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.

h2. Restricţii
* $1 ≤ N, M ≤ 100 000$

* Pentru $50%$ din teste, $N ≤ 1000$.

h2. Exemplu