Arbre en grups de tres P81908

Donat un arbre, en podeu esborrar algunes arestes de manera que els components connexos resultants tinguin tots tres vèrtexs? Aquí, un arbre és un graf no dirigit, connex i sense cicles.

Entrada

L’entrada consisteix en diversos casos, cadascun amb el nombre de vèrtexs n, seguit de les n − 1 arestes x y, amb x ≠ y. Suposeu 6 ≤ n < 10⁵, que els vèrtexs es numeren a partir de 0, que les arestes donades realment formen un arbre, i que n és múltiple de 3.

Sortida

Per a cada cas, si no hi ha solució, escriviu una línia amb “NO”. Altrament, escriviu una línia amb “SI”, seguida de totes les arestes esborrades, una per línia. Els dos vèrtexs de les arestes han d’estar ordenats, i les arestes han de sortir ordenades lexicogràficament.