Fişierul intrare/ieşire:tree2.in, tree2.outSursăStelele Informaticii 2006, clasele 11-12
AutorMugurel Ionut AndreicaAdăugată debogdan2412Bogdan-Cristian Tataroiu •bogdan2412
Timp execuţie pe test0.825 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Tree 2

Patratul unui graf neorientat G este un graf G2 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 G2 si cunoscand faptul ca G este un arbore (un graf neorientat, conex, care nu contine cicluri), determinati graful G.

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 G2. Urmatoarele M linii contin cate doua numere intregi A si B, avand semnificatia ca exista muchie intre nodul A si nodul B in G2. Intre doua noduri va exista cel mult o muchie.

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.

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.

Exemplu

tree2.intree2.out
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
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content