[AdditionalFile3546.zip](file://AdditionalFile3546.zip?type=additional_file)

#3546. 「COCI 2021.10」Logičari

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2021/2022 Contest #1 T3「Logičari」

给定一个 $n$ 个点的基环树，现在对基环树上的点染色，使得每个点都有且仅有一个与他相连的点（不包括它自身）被染色，求最少的染色点数，或者返回无解。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，一行两个整数 $u_i,v_i$，表示 $u_i$ 与 $v_i$ 间有一条边。

输出格式

输出最小的染色点数，或者返回无解，无解输出 -1。

样例 1

输入

4
1 2
2 3
3 4
4 1

输出

2

可以在 $1,2$ 号点染色。

样例 2

输入

3
1 2
2 3
3 1

输出

-1

如果有一个点被染色，则被染色的点不会有被染色的相邻的点。

如果有两个点被染色，则不被染色的点会有两个被染色的相邻的点。

样例 3

输入

7
1 2
2 3
3 4
4 5
5 6
6 7
2 4

输出

4

数据范围与提示

对于全部数据，$3\le n\le 10^5$，$1\le u_i,v_i\le n$。