Arbres diferents P70214

0.58 Els professors d’Algorísmia ja no saben què fer perquè algú aprovi. Desesperats, en un examen teòric només van demanar que es dibuixés un arbre, a veure si d’aquesta manera...

Tres estudiants van fer això: El primer, que no sabia ni què se li preguntava, va dibuixar un arbre de la natura (en concret, un roure). Com a premi va obtenir una nota negativa.

0.42

El segon estudiant sí que va dibuixar el que calia, és a dir, un graf no dirigit, connex i acíclic. Malgrat els esforços dels professors per evitar còpies, el tercer estudiant va aconseguir veure l’arbre que havia dibuixat el segon estudiant. Això sí, després va haver de dibuixar un altre arbre que fos suficientment diferent, perquè el Roura no el suspengués per copiar.

Formalment, donat un arbre $A$ amb vèrtexs $1, \dots, n$, sigui $g_A(x)$ el grau (el nombre de veïns) del vèrtex $x$ dins d’$A$. Diem que dos arbres $A$ i $B$ són suficientment diferents si, per a tota $1 \le x \le n$, es compleix $g_A(x) \ne g_B(x)$.

Donat un arbre $A$ amb $n$ vèrtexs, existeix algun arbre $B$ que també tingui $n$ vèrtexs i que sigui suficientment diferent?

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$, seguida d’$n - 1$ arestes $x$ $y$. Suposeu $2 \le n \le 10^5$, que els vèrtexs es numeren entre 1 i $n$, i que les arestes donades realment formen un arbre.

Sortida

Per a cada arbre donat, escriviu “SI” si existeix un arbre amb el mateix nombre de vèrtexs suficientment diferent, o “NO” altrament.