Problem Description

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.

Input Format

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 Format

Output the minimum number of colored vertices, or report that there is no solution. If there is no solution, output -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

Hint

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

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 Contest #1.

Translated by ChatGPT 5