Petya and Vasya enthusiastically play spies. Today they are planning where they will be
located their secret bunkers and headquarters.
So far, Petya and Vasya have decided that they will need exactly n bunkers, which will be numbered from 1 to n for secrecy.
Some of them will be connected by two-way tunnels, and for reliability and secrecy, the tunnels will be accessible from any bunker to any one way.
Petya and Vasya even decided which of the bunkers will be connected by tunnels, but they cannot choose which one will be the headquarters.
The boys want to choose it and divide the remaining bunkers among themselves so that they get an equal number of bunkers. Exactly two tunnels lead to the headquarters: one from the bunker belonging to Vasya, the other from the bunker belonging to Petya.
Tired Petya went to his house, and in the morning Vasya showed him a plan on which the bunkers were marked with dots and the tunnels with segments.
In addition, Vasya chose the headquarters in such a way that the plan he drew was symmetrical with respect to a straight line passing through the point that corresponded to the headquarters.
Although Petya almost immediately showed Vasya that he had made a mistake and did not draw half of the bunkers, he wondered if it was possible to choose a headquarters and draw such a symmetrical plan.
Input:
The first line of the input file contains a single integer n (1 <= n <= 10
5) - the number of bins.
The next n - 1 lines contain two integers u
i and v
i (1 <= u
i, v
i <= n, u
i ≠ v
i) - numbers of bunkers connected by the i-th tunnel.
It is guaranteed that there is only one path between any two bunkers.
Output:
In the output file print "YES" if it is possible to choose a headquarters and draw such a plan, or "NO" if that's not possible.
Examples:
| Input |
Output |
2
1 2
| NO |
3
1 2
2 3
| YES |