| Fişierul intrare/ieşire: | mesaj4.in, mesaj4.out | Sursă | Stelele Informaticii 2010 |
| Autor | Din Folclor | Adăugată de |  Paul-Dan Baltescu •pauldb |
| Timp execuţie pe test | 0.225 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | mesaj4.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 |
