题目描述

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

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

输入格式

第一行一个整数 $n$。

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

输出格式

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

4
1 2
2 3
3 4
4 1

2

3
1 2
2 3
3 1

-1

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$。