题目描述

给定一个 $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

提示

样例解释

样例 1 解释

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

样例 2 解释

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

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

数据范围

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

说明

本题总分 $110$ 分。

本题译自 Croatian Open Competition in Informatics 2021/2022 Contest #1 T3 Logičari。