Bunkers#2784
Petya and Vasya are enthusiastically playing spies. Today they are planning where to place their secret bunkers and headquarters.
They have decided that they need exactly bunkers, which will be numbered from to for secrecy. Some of these bunkers will be connected by bidirectional tunnels in such a way that, for both reliability and secrecy, there is a unique path between any two bunkers. Petya and Vasya have already determined which bunkers will be connected by tunnels, but they cannot decide which one will serve as the headquarters.
They want to choose a headquarters and divide the remaining bunkers between themselves, so that each gets an equal number of bunkers and there are exactly two tunnels going to the headquarters: one from a bunker belonging to Vasya, and the other from a bunker belonging to Petya.
After a long day, Petya went home, and in the morning Vasya showed him a plan where the bunkers were marked as points and tunnels as lines. Vasya had selected the headquarters so that the plan was symmetric with respect to the line passing through the point representing the headquarters.
Although Petya immediately pointed out that Vasya had made a mistake and had not drawn half of the bunkers, he became interested in whether it is possible to choose a headquarters and draw such a symmetric plan.
The first line of the input contains a single integer (1 \leq n \leq 10^5) — the number of bunkers. The next n-1 lines each contain two integers u_i and v_i (1 \leq u_i, v_i \leq n, u_i \ne v_i) — the numbers of the bunkers connected by the -th tunnel. It is guaranteed that there is a unique path between any two bunkers.
Print YES if it is possible to choose a headquarters and draw such a symmetric plan, or NO if it is not possible.
Example 1