linegraph

Cătălin, după ce s-a jucat destul la bunici, a ajuns acasă, dar nu a venit cu mâna goală, ci a adus cu el cel mai frumos arbore pe care l-a avut în jocul “TreeGCD”, desenat pe o hârtie. Acasă, fratele lui mai mic a găsit această foaie și s-a gândit să își încerce talentul la desen. El vrea să transforme arborele într-un graf în următorul fel: fiecare muchie din arborele inițial devine un nod în noul graf, două noduri din noul graf sunt legate printr-o muchie dacă și numai dacă cele două muchii corespunzătoare din arborele inițial au un nod în comun.

După ce a construit acest graf, el a aruncat hârtia cu arborele inițial. Când s-a întors de la școală, Cătălin, văzând ceea ce s-a întâmplat, nu a fost prea fericit. Din fericire, a aflat că voi puteți să reconstruiți arborele inițial, dacă vă dă graful.

Cerință

Se dau numărul N de noduri, numărul M de muchii și cele M muchii din graf. Reconstruiți arborele inițial.
Este posibil ca fratele lui Cătălin să fi desenat greșit graful și să nu existe un arbore asociat.

Date de intrare

În fișierul de intrare linegraph.in pe prima linie se află un număr T, ce reprezintă numărul de teste din fișier. Pentru fiecare test pe prima linie se află două numere naturale N și M separate prin spaţiu cu semnificațiile din enunț, iar pe următoarele M linii se află câte două numere separate prin spaţiu, ce reprezintă nodurile care au o muchie între ele.

Date de ieșire

În fișierul de ieșire linegraph.out pe prima linie trebuie să se afișeze fie cuvântul NU, dacă nu există un arbore asociat grafului dat, fie cuvântul DA, dacă există arbore asociat, şi în acest caz pe următoarea linie se va afişa un număr E, ce reprezintă numărul de noduri din arbore, și pe următoarele E-1 linii se vor afişa câte două numere ce reprezintă perechile de noduri din arbore, care au o muchie între ele.

Restricții

• 1 ≤ T ≤ 10.000;
• 1 ≤ N ≤ 1.000;
• $0 ≤ M ≤ \frac{N(N-1)}{2}$
• suma pătratelor tuturor N-urilor din fişierul de intrare nu depăşeşte 1.000.000;
• pentru teste în valoare de 15 puncte, se garantează că există soluție și că arborele din care s-a construit graful are fie formă de lanț, fie are N-1 frunze;
• pentru alte teste în valoare de 55 de puncte, se garantează că N ≤ 100 şi suma pătratelor tuturor N-urilor din fişierul de intrare nu depăşeşte 10.000;
• dacă există mai multe soluţii, se poate afişa oricare dintre ele;
• arborele din fişierul de ieşire cu E noduri va avea nodurile numerotate cu 1,2,...,E;
• numerotarea efectivă a nodurilor din fişierul de ieşire nu este importantă – orice soluţie ce renumerotează nodurile va fi considerata un răspuns corect.

Exemplu

linegraph.in

2
5 7
3 2
3 5
3 1
2 5
2 1
1 5
1 4
3 1
1 2

linegraph.out

DA
6
1 2
1 3
3 4
3 5
3 6
NU

Explicații

În fişierul de intrare avem un graf. Fiecărei muchii din acest graf îi corespunde un nod din arborele din fişierul de ieşire. Astfel: muchia (1,3) devine nodul 1, muchia (1,2) devine nodul 4, muchia (3,4) devine nodul 3, muchia (3,5) devine nodul 2 și muchia (3,6) devine nodul 5.
Muchiile (1,3), (3,4), (3,5), (3,6) au toate nodul comun 3, deci nodurile lor corespunzătoare din graf (1,3,2,5) au toate muchii între ele.

În al doilea test nodul 3 este izolat şi graful nu poate proveni din niciun arbore.