h2. Restricţii

* $... ≤ ... ≤ ...$

* $1$ ≤ $T$ ≤ $10.000$
* $1$ ≤ $N$ ≤ $1.000$
* $0$ &le; $M$ &le; <tex> \frac{N*(N-1)}{2} </tex>

* 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$;

* 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.
h2. Exemplu
table(example). |_. linegraph.in |_. linegraph.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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

|
h3. Explicaţie

...

În fişierul de intrare avem un graf. Fiecărei muchii dinacest 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.

== include(page="template/taskfooter" task_id="linegraph") ==