[COCI2021-2022#1] Logičari
题目描述
给定一个 $n$ 个点的基环树,现在对基环树上的点染色,使得每个点都有且仅有一个与他相连的点(不包括它自身)被染色,求最少的染色点数,或者返回无解。
输入输出格式
输入格式
第一行一个整数 $n$。
接下来 $n$ 行,一行两个整数 $u_i,v_i$,表示 $u_i$ 与 $v_i$ 间有一条边。
输出格式
输出最小的染色点数,或者返回无解,无解输出 `-1`。
输入输出样例
输入样例 #1
4
1 2
2 3
3 4
4 1
输出样例 #1
2
输入样例 #2
3
1 2
2 3
3 1
输出样例 #2
-1
输入样例 #3
7
1 2
2 3
3 4
4 5
5 6
6 7
2 4
输出样例 #3
4
说明
#### 样例解释
#### 样例 1 解释
可以在 $1,2$ 号点染色。
#### 样例 2 解释
如果有一个点被染色,则被染色的点不会有被染色的相邻的点。
如果有两个点被染色,则不被染色的点会有两个被染色的相邻的点。
#### 数据范围
对于全部数据,$3\le n\le 10^5$,$1\le u_i,v_i\le n$。
| Subtask | 特殊限制 | 分数 |
| :-----: | :----------------: | :--: |
| $1$ | 每个点的点度为 $2$ | $10$ |
| $2$ | $n\le 20$ | $10$ |
| $3$ | $n\le 10^3$ | $40$ |
| $4$ | 无特殊限制 | $50$ |
#### 说明
**本题总分 $110$ 分。**
本题译自 [Croatian Open Competition in Informatics 2021/2022](https://hsin.hr/coci/archive/2021_2012) [Contest #1](https://hsin.hr/coci/archive/2021_2022/contest1_tasks.pdf) T3 Logičari。