Deep within a forest lies an ancient tree, home to $$$n$$$ ants living in $$$n$$$ tiny houses, indexed from $$$1$$$ to $$$n$$$, connected by the branches of the tree.
Once a year, all the ants need to gather to watch the EUC. For this, all ants move along the $$$n-1$$$ branches of the tree they live on to meet at the home of one ant.
However, this year the ants could not agree on where to meet and need your help to gather up. You can tell all the ants currently at house $$$u$$$ to move to house $$$v$$$ if there is a branch directly connecting those two houses. However, the ants ignore your command if there are fewer ants gathered in house $$$v$$$ than in house $$$u$$$, i.e., if it would be easier for the ants from house $$$v$$$ to move. This even holds true if no ant at all is currently in house $$$v$$$. You can give this kind of commands as many times as you want.
Is it possible for you to gather all the ants in a single house?
The first line contains one integer $$$n$$$ ($$$1\leq n\leq 200\,000$$$) — the number of ant homes.
Each of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1\leq u, v\leq n$$$) — there is a branch directly connecting the house $$$u$$$ and house $$$v$$$. It is guaranteed that every ant can reach the house of any other ant just by following the branches of the tree.
Print $$$\texttt{YES}$$$ if it is possible to gather all the ants in a single house. Otherwise, print $$$\texttt{NO}$$$.
75 13 24 63 67 11 3
YES
51 44 23 25 3
NO
64 55 66 12 63 2
YES
In the first sample, you can gather all the ants at house $$$3$$$ as follows:
In the second sample, it is impossible to gather all the ants in a single house.
Name |
---|