John and tree game
Description
John is tired after working hard all day, so he decides to relax by playing a game.
In this game, John has a tree with $N$ nodes. John can pair $2$ different nodes together if and only if the distance between them is even. Each node can belong to at most one pair.
John can win the game if he can pair all the nodes of the tree. Find out if he can win the game.
* The distance between two nodes is defined as the number of edges on the unique simple path between them.
The first line contains an integer $N$ $(1 \leq N \leq 5 \cdot 10^5)$ - the number of nodes of the tree.
Each of the next $N - 1$ lines contain two integers $u$ and $v$ $(1 \leq u, v \leq N; u \neq v)$ denoting there is an undirected edge between node $u$ and node $v$. It is guaranteed that the given edges form a tree.
Output "YES" (without quotes) if John can win the game, and "NO" (without quotes) otherwise.
You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
Input
The first line contains an integer $N$ $(1 \leq N \leq 5 \cdot 10^5)$ - the number of nodes of the tree.
Each of the next $N - 1$ lines contain two integers $u$ and $v$ $(1 \leq u, v \leq N; u \neq v)$ denoting there is an undirected edge between node $u$ and node $v$. It is guaranteed that the given edges form a tree.
Output
Output "YES" (without quotes) if John can win the game, and "NO" (without quotes) otherwise.
You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
3
2 1
3 2
6
4 2
6 5
3 5
5 1
4 5
NO
YES
Note
In the first test case, we can only pair $(1, 3)$, but we can't pair the node $2$, so the answer is no.
In the second test case, we can have the following pairs $(1, 6)$, $(3, 4)$, $(5, 2)$, so the answer is yes.