+ Time limit: 1 second + Memory limit: 256 megabytes ---------- Uncle (Amou) and Guru are in trouble. The story began when Uncle harvested an $n$-vertex tree from his backyard and started examining it, noticing that every edge of the tree has two states: open or closed. Initially, all edges of the tree were open. Astonished by this capability of his tree, he took the tree to Guru to play a game together. Guru, who saw happiness in being single (unrestricted/a leaf node), placed a token on vertex $1$ of the tree and defined the game on the tree as follows: In every turn of the game, if the token is currently on a vertex with degree $1$, Guru wins the game. Otherwise, Uncle first selects one of the open edges of the tree and closes it. If all edges of the tree are closed, he does nothing. Then it becomes Guru's turn. Guru, in his turn, can select one of the open edges connected to the vertex where the token is located and move the token to the other end of that edge. If none of the edges connected to the token's vertex are open, Uncle wins the game. Uncle, having been defeated in several rounds, became angry and left the location after arguing with Guru. Now that he has regained his composure, he provides you with the tree information and asks who would win the game if both players played optimally. # Input The first line of the input contains the number $n$, the number of vertices in the tree. In each of the next $n - 1$ lines, two numbers $u, v$ are given, indicating the existence of an edge between vertices $u$ and $v$ in the tree. # Output If both players play optimally, output $1$ if Guru wins the game, and $0$ if Uncle wins the game. # Constraints $$ 1 \leq n \leq 10^5 $$ $$ 1 \leq u , v \leq n $$ ## Sample Input 1 ``` 6 1 2 2 3 2 4 1 5 5 6 ``` ## Sample Output 1 ``` 0 ``` Uncle can first close the edge between vertices $1$ and $2$. In this case, Guru is forced to move the token to vertex $5$. Since the degree of $5$ is greater than $1$, the game continues. At this stage, Uncle can close the edge between vertices $5$ and $6$, forcing Guru to return the token to vertex $1$. Then, by closing the edge between vertices $1$ and $5$, he wins the game, because Guru can no longer move the token. Consequently, Uncle wins the game. ## Sample Input 2 ``` 7 1 2 2 3 2 4 1 5 5 6 5 7 ``` ## Sample Output 2 ``` 1 ``` In this example, no matter how Uncle plays, Guru can move the token to a degree $1$ vertex. Consequently, Guru wins.