Problem 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  and vertice i.(The length of each edge is ). 

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  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  testcases. 

For each testcase, the first line contains a number n(≤n≤).

Then n− lines follow. Each line contains two numbers u,v(≤u,v≤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

Sample Output

YES

NO

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <algorithm>

 #include <queue>

 #include <math.h>

 using namespace std;

 #define INF 0x3f3f3f3f

 #define ll long long

 #define met(a,b) memset(a,b,sizeof(a));

 #define N 1034

 int Map[N][N];

 int con[N];

 int n;

 void bfs(int s,int m)

 {

     con[s]=m;

     for(int i=;i<=n;i++)

     {

         if(Map[s][i]&&!con[i])

         {

             bfs(i,m+);

         }

     }

 }

 int main()

 {

     int a,b;

     int sum[N];

     while(scanf("%d",&n)!=EOF)

     {

         met(Map,);met(con,);

         for(int i=;i<n;i++)

         {

             scanf("%d %d",&a,&b);

             Map[a][b]=Map[b][a]=;

         }

         bfs(,);///对树分层

         met(sum,);int ans=;

         for(int i=;i<=n;i++)

         {

             sum[con[i]]++;

         }

         for(int i=;i<=n;i++)

         {

             if(sum[i]==)///是否是一条线到底

                 ans++;

             else

             {

                 if(sum[i+]==)///是否是扫帚型

                     ans=n;

                     break;

             }

         }

         if(ans==n)

             printf("YES\n");

         else

             printf("NO\n");

     }

     return ;

 }