Bunkers

Interview

Time limit2sMemory limit1024 MB

Summary

Given a tree of n nodes, decide whether one vertex has degree 2 and its two branches are equal-sized mirror images.

Level: Medium5 of 10
Topics: Tree, Hash map, DFS
Solved: No attempts yet

Problem

Petya and Vasya play spies with great enthusiasm. Today they plan where their secret bunkers and headquarters will be.

They decided they need exactly $n$ bunkers, numbered from $1$ to $n$ for secrecy. Some of them will be connected by two-way tunnels, and for reliability and secrecy, any bunker can be reached from any other bunker in exactly one way. The boys have already decided which bunkers are connected, but they cannot choose which bunker becomes the headquarters. They want to pick it and split the remaining bunkers between themselves so that each gets the same number of bunkers, and exactly two tunnels lead to the headquarters: one from a bunker belonging to Vasya, and one from a bunker belonging to Petya.

The tired Petya went home, and in the morning Vasya showed him a plan where bunkers were drawn as points and tunnels as segments. Vasya also chose the headquarters so that the plan is symmetric about a line passing through the point that stands for the headquarters.

Petya quickly pointed out that Vasya had drawn only half of the bunkers. He then wondered whether it is possible to choose a headquarters and draw such a symmetric plan.

Input

The first line contains one integer $n$ ( $1 \le n \le 10^5$ ), the number of bunkers. Each of the next $n - 1$ lines contains two integers $u_i$ and $v_i$ ( $1 \le u_i, v_i \le n, u_i \ne v_i$ ), the numbers of the bunkers joined by the $i$ -th tunnel. It is guaranteed that there is exactly one path between any two bunkers.

Output

Print YES if it is possible to choose the headquarters and draw such a plan, or NO if it is impossible.

Examples2

Example 1
Input
```
2
1 2
```
Expected output
```
NO
```
Example 2
Input
```
3
1 2
2 3
```
Expected output
```
YES
```