tree2

Tree 2

== include(page="template/taskheader" task_id="tree2") ==

Poveste si cerinta...

Patratul unui graf neorientat $G$ este un graf $G^2^$ care are aceeasi multime de varfuri ca si $G$ si care contine o muchie $(u, v)$ intre o pereche de varfuri $u$ si $v$ daca si numai daca exista un drum avand o lungime de cel mult $2$ muchii intre $u$ si $v$ in $G$.
 
Dandu-se $G^2^$ si cunoscand faptul ca $G$ este un arbore (un graf neorientat, conex, care nu contine cicluri), determinati graful $G$.

h2. Date de intrare

...

Fisierul de intare $tree2.in$ contine pe prima linie numerele intregi $N$ si $M$, reprezentand numarul de noduri, respectiv numarul de muchii din $G^2^$. Urmatoarele $M$ linii contin cate doua numere intregi $A$ si $B$, avand semnificatia ca exista muchie intre nodul $A$ si nodul $B$ in $G^2^$. Intre doua noduri va exista cel mult o muchie.

h2. Date de iesire

...

In fisierul de iesire $tree2.out$ veti afisa $N - 1$ linii, corespunzand celor $N - 1$ muchii ale lui $G$. Pe fiecare din aceste linii veti afisa doua numere intregi $A$ si $B$, avand semnificatia ca exista muchie intre nodurile $A$ si $B$ in $G$. Muchiile pot fi afisate in orice ordine.

h2. Restrictii

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

* $2 ≤ N ≤ 333$
* Nodurile sunt numerotate de la $1$ la $N$.
* Se garanteaza ca va exista cel putin un arbore $G$ al carui patrat sa fie graful dat in fisierul de intrare. In cazul in care exista mai multe solutii, puteti afisa oricare dintre ele.

h2. Exemplu
table(example). |_. tree2.in |_. tree2.out |

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

| 9 19
1 2
1 3
1 4
1 5
2 3
2 4
2 5
2 9
3 4
3 5
3 6
3 7
3 8
3 9
4 5
4 8
5 6
5 7
6 7
| 1 3
2 3
2 9
3 4
3 5
4 8
5 6
5 7

|

 
h3. Explicatie
 
...

| 6 9
1 2
1 3
1 5
2 5
3 4
3 5
3 6
4 5
4 6
| 3 4
1 2
3 5
5 1
6 4
|

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

1694