P7929 [COCI 2021/2022 #1] Logičari

Given a unicyclic graph with $n$ vertices, you now need to color some vertices so that every vertex has exactly one adjacent vertex (excluding itself) that is colored. Find the minimum number of colored vertices, or report that there is no solution.

The first line contains an integer $n$. The next $n$ lines each contain two integers $u_i, v_i$, meaning there is an edge between $u_i$ and $v_i$.

Output the minimum number of colored vertices, or report that there is no solution. If there is no solution, output `-1`.

#### Sample Explanation #### Sample 1 Explanation You can color vertices $1$ and $2$. #### Sample 2 Explanation If there is one colored vertex, then the colored vertex will have no colored adjacent vertex. If there are two colored vertices, then an uncolored vertex will have two colored adjacent vertices. #### Constraints For all testdata, $3 \le n \le 10^5$, $1 \le u_i, v_i \le n$. | Subtask | Special Constraints | Score | | :-----: | :-----------------: | :---: | | $1$ | The degree of every vertex is $2$ | $10$ | | $2$ | $n \le 20$ | $10$ | | $3$ | $n \le 10^3$ | $40$ | | $4$ | No special constraints | $50$ | #### Notes **The total score for this problem is $110$ points.** This problem is translated from T3 Logičari of [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). Translated by ChatGPT 5