Rikka with Tree

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

For a tree $T$, let $F(T,i)$ be the distance between vertice 1 and vertice $i$.(The length of each edge is 1).

Two trees $A$ and $B$ are similiar if and only if the have same number of vertices and for each $i$ meet $F(A,i)=F(B,i)$.

Two trees $A$ and $B$ are different if and only if they have different numbers of vertices or there exist an number $i$ which vertice $i$ have different fathers in tree $A$ and tree $B$ when vertice 1 is root.

Tree $A$ is special if and only if there doesn't exist an tree $B$ which $A$ and $B$ are different and $A$ and $B$ are similiar.

Now he wants to know if a tree is special.

It is too difficult for Rikka. Can you help her?

Input

There are no more than 100 testcases.

For each testcase, the first line contains a number $n(1 \leq n \leq 1000)$.

Then $n-1$ lines follow. Each line contains two numbers $u,v(1 \leq u,v \leq n)$ , which means there is an edge between $u$ and $v$.

Output

For each testcase, if the tree is special print "YES" , otherwise print "NO".

Sample Input

3 1 2 2 3 4 1 2 2 3 1 4

Sample Output

YES NO
Hint
For the second testcase, this tree is similiar with the given tree: 4 1 2 1 4 3 4

Hint

hujie

Source

BestCoder Round #53 (div.2)

提交代码