Minimum Colored Nodes in a Unicyclic Graph

Given a unicyclic graph with n vertices and n edges (i.e. a tree augmented with one extra edge, so that there is exactly one simple cycle), you are to color some vertices. The coloring must satisfy the following condition: for every vertex \(v\), exactly one of its neighbors is colored. In other words, if \(N(v)\) denotes the set of neighbors of \(v\), then

[ #{u\in N(v): u \text{ is colored}} = 1 \quad \text{for every } v=1,2,\dots,n. ]

Your task is to choose a subset \(S\) of vertices (the colored ones) with the minimum possible size satisfying the above condition, or determine that no such subset exists. If no solution exists, output \(-1\).

inputFormat

The first line contains an integer \(n\) (the number of vertices). The vertices are numbered from \(1\) to \(n\). Since the graph is a unicyclic graph, it has exactly \(n\) undirected edges. Each of the next \(n\) lines contains two integers \(u\) and \(v\) indicating that there is an edge between \(u\) and \(v\>.

outputFormat

Print a single integer: the minimum number of colored vertices required to satisfy the condition, or \(-1\) if no valid coloring exists.

sample

3
1 2
2 3
3 1

-1