Cerință
Tim Goodman și Detective Pikachu investighează sursa misteriosului gaz care face pokemonii din Ryme City să devină sălbatici. Dupa o lungă sesiune de interogatoriu cu un Mr. Mime necooperativ, au reusit să afle câteva informații prețioase.
Sub Ryme City există o retea formată din puncte de control numerotate de la la , unite între ele prin tuneluri bidirecționale, astfel încât există un drum unic între oricare două puncte de control și , Mr. Mime a mers pe cel mai scurt drum și își amintește concentrația minimă a gazului pe care a întalnit-o în punctele de control de pe acel drum.
Ultima informație dată de Mr. Mime este că, foarte probabil, toate mai putin două dintre punctele de control au exact două tuneluri adiacente.
Pentru a continua investigația, Tim și Detective Pikachu trebuie să afle o formă posibilă a rețelei de tuneluri bazată pe informațiile oferite de Mr. Mime.
Date de intrare
Fişierul de intrare detective.in conține pe prima linie și , reprezentând numărul de puncte de control, respectiv numărul de informații despre rețea. Pe linia avem tripletele reprezentând informațiile oferite de Mr. Mime.
Date de ieșire
Fişierul de ieșire detective.out va conține perechi , reprezentând două puncte de control unite de un tunel.
Restricții și precizări
- ;
- Pentru teste în valoare de de puncte, ,
- Pentru alte teste în valoare de puncte, , , oricare ar fi există un drum parcurs de Mr. Mime astfel încât și
Exemplu
detective.in
5 10
3 0 0
3 4 0
3 1 0
3 2 0
0 4 0
0 1 0
0 2 0
4 1 1
4 2 1
1 2 1
detective.out
3 0
0 4
4 1
1 2
Explicație
O posibilă retea de tuneluri si puncte de control este reprezentată în următoarea imagine:
Următoarea retea reprezentată nu este însă corectă deoarece concentratia minimă de gaz observată de Mr. Mime pe drumul de la la este , dar reteaua ar indica că această concentrație este , fiind minimul dintre concentratiile de pe drum ( si ).
