Fişierul intrare/ieşire:revolve.in, revolve.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 16
AutorLucian BicsiAdăugată deAGMinformaticaAGMInformatica AGMinformatica
Timp execuţie pe test1 secLimită de memorie66048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Revolve

"Toate drumurile duc in parc."

(Chirescu, 2016)

Ionica si Chirescu sunt doi prieteni foarte buni. In tineretile lor, in fiecare zi porneau in Bucuresti in cautarea a ceva de facut. Fiecare dintre ei isi alegea un punct din plecare oarecare si ajungeau, bineinteles, intr-un final, in parcul din Piata Unirii, unde ciocneau un pahar de lapte cald. Traseele lor erau mereu foarte specifice: de fiecare data alegeau drumul cel mai scurt spre parc din punctul in care se aflau. Din fericire pentru acestia, acest lucru era mereu foarte simplu, deoarece harta Bucurestiului era conexa si nu avea niciun ciclu! (cu alte cuvinte, era un arbore)

Deoarece cei doi sunt prieteni foarte buni, de fiecare data cand unul dintre cei doi ajungea intr-un loc in care urma sa ajunga si cel de-al doilea, il astepta cu nerabdare, dupa care isi continuau amandoi drumul linistiti spre parc. Acel loc putea fi fie parcul in sine, fie un loc intermediar.

Acum Ionica si Chirescu sunt adulti responsabili. Chiar astazi s-au intalnit la locuinta rezindentiala a lui Ionica din Silicon Valley si isi rememoreaza amintirile. Acestia isi amintesc M zile (din cele multe pe care le petreceau impreuna). Ei nu isi mai amintesc exact locatia exacta a parcului, dar pentru fiecare zi din cele M cunosc cele doua puncte de plecare a, b, respectiv punctul in care cei doi se intalnesc, notat in problema noastra cu c.

Cerinta

Dandu-se numarul de locuri intermediare N, respectiv numarul de zile, M, impreuna cu punctele de plecare si locul de intalnire, reconstituiti harta Bucurestiului din tineretile celor doi prieteni. Cei doi stiu ca solutia nu e neaparat unica, asa ca o accepta pe cea care va place mai mult :). Daca cei doi isi amintesc gresit zilele (ceea ce e foarte probabil), afisati -1.

Date de intrare

Fişierul de intrare revolve.in va contine pe primia linie T, numarul de teste.
Vor urma mai apoi T configuratii de tipul:

  • N M (numarul de locatii intermediare, respectiv numarul de zile)
  • M linii, fiecare continand un triplet de forma a b c, cu semnificatiile din enunt

Date de ieşire

Pentru fiecare test, afisati in fisierul revolve.out (pe linii separate, ca in exemplu):

  • B, un numar natural ce indica locatia parcului Unirii (1 <= B <= N)
  • N-1 linii, fiecare linie continand cate o pereche a b cu semnificatia ca exista un drum direct de la nodul a la nodul b (1 <= a, b <= N).

Daca nu exista nicio harta posibila, atunci se va afisa -1

Restricţii

  • T <= 25
  • N, M <= 100,000
  • Suma tuturor M-urilor este mai mica sau egala cu 500,000
  • Suma tuturor N-urilor este mai mica sau egala cu 500,000
  • Constructia afisata trebuie sa respecte conditiile din enunt!
  • In toate locatiile intermediare se afla magazine aprovizionate cu lapte proaspat, in caz ca unul din cei doi este nerabdator si isi bea laptele pe drum!

Exemplu

revolve.inrevolve.out
2
4 3
1 2 1
2 3 1
3 4 3
2 2
1 2 1
1 2 2
1
1 2
1 3
4 3
-1

Explicaţie

Sunt 2 teste.

In primul test, o solutie posibila este ca parcul sa fie amplasat in nodul 1, iar celelalte locatii ca in output.

Pana si Ionica se prinde ca in al doilea test, nu exista o harta posibila cu proprietatile din enunt.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?