题目描述

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

注：基环树是一个 $n$ 个点、$n$ 条边的连通无向图。

输入格式

第一行一个整数 $n$。

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

输出格式

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

4
1 2
2 3
3 4
4 1

2

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

3
1 2
2 3
3 1

-1

如果有一个点被染色，则被染色的点不会有被染色的相邻的点（不满足条件）。

如果有两个点被染色，则不被染色的点会有两个被染色的相邻的点（不满足条件）。

数据规模与约定

对于全部数据：

• $3 \le n \le 10^5$

• $1 \le u_i, v_i \le n$