Arbres diferents P20665

En aquest problema considerem arbres, és a dir, grafs no dirigits, connexs i sense cicles. 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 en 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, si no existeix cap arbre amb el mateix nombre de vèrtexs que en sigui suficientment diferent, escriviu “NO”. Altrament, escriviu “SI” seguit de les $n - 1$ arestes de l’arbre, en qualsevol ordre. També podeu triar l’ordre dels dos vèrtexs de cada aresta. Si hi ha més d’una solució possible, escolliu la que vulgueu. Seguiu estrictament el format dels exemples.