Ministrul va cere sa ii spuneti ce grad de curatenie ar trebui sa aiba fiecare oras pentru a fi respectate toate restrictiile. Gradele de curatenie pot fi si negative( ministrul manuieste exceptional ranga si tomberonul). Pentru a va ajuta el va mai dezvaluie $2$ proprietati ale traseelor posibile:
* daca $2$ trasee se intersecteaza, atunci unul este inclus in celalalt

* daca $x$ si $y$ sunt cele mai apropiate $2$ puncte ale traseelor $[a, b]$ si $[c, d]$, atunci $x$ apartine multimii ${a, b}$ si $y$ apartine multimii ${c, d}$( prin notatia $[a, b]$ intelegem traseul care incepe in orasul $a$, iar ultimul sau nod parcurs este orasul $b$)

* daca $x$ si $y$ sunt cele mai apropiate $2$ puncte ale traseelor $[a, b]$ si $[c, d]$, atunci $x$ apartine multimii ${a, b}$ si $y$ apartine multimii ${c, d}$, sau invers( prin notatia $[a, b]$ intelegem traseul care incepe in orasul $a$, iar ultimul sau nod parcurs este orasul $b$)

h2. Date de intrare

h2. Restricţii
* $1 ≤ N ≤ 10000$

* $0 ≤ M ≤ numarul maxim de trasee posibile$

* $0 ≤ M ≤ numarul de maxim de trasee posibile$

* Nu este neaparat ca Ciob sa poata pleca din orasul in care aterizeaza.
* Se garanteaza ca exista solutie pentru datele de test.
* Se garanteaza ca nu vor exista 2 drumuri identice( ca noduri) in fisierul de intrare.

5934