Problem Description

Given a cycle-rooted tree with $n$ vertices, you need to color the vertices such that each vertex has exactly one adjacent vertex (excluding itself) colored. Determine the minimum number of colored vertices, or return "No solution" if it's not possible.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain two integers $u_i$ and $v_i$, indicating an edge between $u_i$ and $v_i$.

Output Format

Output the minimum number of colored vertices, or output -1 if there is no solution.

Sample Input and Output

Sample Input #1

4
1 2
2 3
3 4
4 1

Sample Output #1

2

Sample Input #2

3
1 2
2 3
3 1

Sample Output #2

-1

Sample Input #3

7
1 2
2 3
3 4
4 5
5 6
6 7
2 4

Sample Output #3

4

Notes

Sample Explanation

Sample 1 Explanation

Vertices 1 and 2 can be colored.

Sample 2 Explanation

If one vertex is colored, the colored vertex will not have an adjacent colored vertex.
If two vertices are colored, the uncolored vertex will have two adjacent colored vertices.

Data Range

For all data, $3 \le n \le 10^5$, $1 \le u_i, v_i \le n$.

This problem is worth a total of 110 points.

This problem is translated from the Croatian Open Competition in Informatics 2021/2022 Contest #1 T3 Logičari.

见题面 Input 部分

见题面 Output 部分