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

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

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

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

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 copiii află toate mesajele. Pe următoarele T linii vor fi afişate câte două numere întregi x şi y.

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