mesaj4

Mesaj4

== include(page="template/taskheader" task_id="mesaj4") ==

Poveste şi cerinţă...

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.

h2. Date de intrare

Fişierul de intrare $mesaj4.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $mesaj4.out$ ...

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$.

h2. Restricţii

* $... ≤ ... ≤ ...$

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

h2. Exemplu
table(example). |_. mesaj4.in |_. mesaj4.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

| 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
|

== include(page="template/taskfooter" task_id="mesaj4") ==

4927