Chase Game on a Tree

Prof. Pang and Prof. Shou play a chase game on a map that is a tree. The map has \(n\) rooms and \(n-1\) bidirectional channels, and is connected (i.e. it forms a tree). Initially, Prof. Pang is in room \(u\) and Prof. Shou is in room \(v\) (with \(u \neq v\)). The players take turns, with Prof. Shou moving first. In each turn, a player may remain in his current room or move to an adjacent room (i.e. one directly connected by an existing channel). The game ends when both are in the same room (i.e. Prof. Pang catches Prof. Shou).

Both professors are very smart. Prof. Pang wishes to catch Prof. Shou in a finite number of turns, while Prof. Shou wishes to avoid being caught indefinitely. To help, Prof. Shou asks Prof. Fei to add some extra channels (i.e. extra edges) so that no matter what initial positions \((u,v)\) are chosen the catch cannot happen in a finite number of turns if Prof. Shou plays optimally. Prof. Fei, being lazy, wants to add as few channels as possible. If no matter how many extra channels are added there always exists a pair of initial rooms \((u,v)\) such that Prof. Pang can eventually catch Prof. Shou, output \(-1\).

Your task is to determine the minimum number of extra channels that must be added so that Prof. Pang cannot catch Prof. Shou in any finite number of turns for any initial positions. All extra channels must connect two distinct rooms that are not already directly connected by a channel. Note that the original map is a tree. It turns out that the answer is closely related to the diameter of the tree.

Observation:

• If the tree has a diameter of at least \(3\) (i.e. there exist two rooms with a distance of at least \(3\)), then adding one extra channel between the two endpoints of a diametral path creates a cycle of length at least \(4\) (in \(\LaTeX\): if \(d \ge 3\), then cycle length = \(d+1\ge 4\)). It is known that in such graphs the cop (Prof. Pang) does not have a winning strategy.
• If the tree has a diameter at most \(2\) (for example, a star graph or a tree with only 2 or 3 nodes), then any extra channel available will create a triangle (a cycle of length \(3\)), and complete graphs (or graphs that are dismantlable) are winning for the cop. Hence, it is impossible to guarantee that Prof. Pang will never catch Prof. Shou and you should output \(-1\).

Task: Given the tree structure, output the minimum number of extra channels required (which will be either \(1\) or \(-1\)).

inputFormat

The first line contains an integer \(n\) (\(2 \le n \le 10^5\)) representing the number of rooms. The following \(n-1\) lines each contain two integers \(u\) and \(v\) (\(1 \le u, v \le n\), \(u \neq v\)) representing a bidirectional channel between room \(u\) and room \(v\). It is guaranteed that the given channels form a tree.

outputFormat

Output a single integer: the minimum number of extra channels required so that no matter what initial positions are chosen, Prof. Pang cannot catch Prof. Shou in a finite number of turns. If it is impossible, output \(-1\).

sample

4
1 2
2 3
3 4

1