Problem Statement

A palindrome is a text that reads the same from right to left as from left to right. Koboshi has grown bored of ordinary palindromes, so she decided to consider ultrapalindromes, which read the same from every direction.

You are given a tree with $N$ vertices numbered from $1$ to $N$. The $i$-th edge connects vertex $a_i$ and vertex $b_i$.

Place $1$ character on each vertex of the tree. A tree with characters placed on it is called an ultrapalindrome if all strings obtained by the following method are equal.

• Choose $2$ distinct vertices $u,v$ of degree $1$, and consider the shortest path from $u$ to $v$. Form a string by arranging the characters placed on the vertices of this path in order from $u$ to $v$.

As an example, consider the tree with characters placed on its vertices as in the figure below. The vertices of degree $1$ are $1,4,5$. The string obtained for $u=1,v=5$ is abe, and the string obtained for $u=5,v=4$ is ebcd. Since the obtained strings differ, this is not an ultrapalindrome.

Determine whether it is possible to make the given tree an ultrapalindrome by placing $1$ character on each of its vertices.

Input

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$

• All inputs are integers.
• $2\le N\le 10^5$
• $1\le a_i,b_i\le N$
• The given graph is a tree.

Output

Print Yes if it can be made an ultrapalindrome, and No if it cannot.

Sample

4
1 2
2 3
2 4

Yes

6
1 3
2 3
3 4
3 6
4 5

No

7
1 2
2 3
3 4
4 5
5 6
6 7

Yes