Fişierul intrare/ieşire:mesaj4.in, mesaj4.outSursăStelele Informaticii 2010
AutorDin FolclorAdăugată depauldbPaul-Dan Baltescu pauldb
Timp execuţie pe test0.225 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Mesaj4

La un joc participă N elevi numerotaţi de la 1 la N. Între elevi s-au format M relaţii de prietenie de forma x y, având semnificaţia că elevul numerotat cu x este prieten cu elevul numerotat cu y şi reciproc. Fiecare elev are un mesaj pe care doreşte să-l transmită tuturor celorlalţi elevi. Pentru a transmite mesajele, la un moment de timp, un singur elev poate alege pe unul dintre prietenii săi şi îi poate spune acestuia toate mesajele pe care le-a aflat până în acel moment. Să se determine timpul minim în care toţi cei N elevi află toate cele N mesaje.

Date de intrare

Fişierul de intrare mesaj4.in va conţine pe prima linie două numere întregi N şi M. Pe următoarele M linii se află câte două numere întregi x şi y, descriind câte o relaţie de prietenie.

Date de ieşire

Fişierul de ieşire mesaj4.out va conţine pe prima linie un număr întreg T, reprezentând timpul minim în care toţi elevii află toate mesajele. Pe următoarele T linii vor fi afişate câte două numere întregi x şi y. Numerele de pe linia i reprezintă faptul că elevul numerotat cu x ii transmite mesajele cunoscute elevului numerotat cu y la momentul i. În cazul în care nu există soluţie, afişaţi -1.

Restricţii

  • 1 ≤ N, M ≤ 100 000
  • Pentru 50% din teste, N ≤ 1000.

Exemplu

mesaj4.inmesaj4.out
6 8
1 2
3 1
2 5
2 3
4 5
5 1
2 6
6 4
10
1 2
3 2
5 4
4 6
2 6
6 4
4 5
5 2
5 1
2 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content