== include(page="template/taskheader" task_id="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 elevii 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 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.
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
