You are given a tree with \(N\) nodes and \(N-1\) edges. Initially, each node is uncolored.
You and your best friend are playing a game by painting the nodes. In this game, you will alternately perform the following operation, starting with yourself:
- Select a node that is not painted yet.
- If it is your turn, paint the node white, otherwise paint the node black.
Then, after all the vertices are colored, the following procedure takes place:
- Repaint every white node that is adjacent to a black node, in black.
Note that all such white nodes are repainted simultaneously, not one at a time.
If there are still one or more white nodes remaining, you win. If all the nodes are now black, your friend wins. Determine the winner of the game, assuming that you will both play optimally.
The first line will contain the integer \(N\ (1 \le N \le 10^5)\).
The next \(N-1\) lines will each contain two integers, \(a_i, b_i\ (1 \le a_i, b_i \le N)\), indicating nodes \(a_i\) and \(b_i\) are connected by an edge. It is guaranteed the entire tree is connected.
First if you win, and
Second if your friend wins.
There are no subtasks for this problem.
Sample Input 1
3 1 2 2 3
Sample Output 1
Sample Input 2
4 1 2 2 3 2 4
Sample Output 2
Sample Input 3
6 1 2 2 3 3 4 2 5 5 6
Sample Output 3