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

* prin notatia $[a, b]$ intelegem traseul care incepe in orasul $a$, iar ultimul sau nod parcurs este orasul $b$. Pentru oricare $2$ trasee posibile disjuncte cele mai apropiate $2$ orase, din punct de vedere al numarului strazilor parcurse de la unul la celalalt, sunt unul dintre capetele primului traseu si unul dintre capetele celui de-al doilea traseu: daca $[a, b]$ si $[c, d]$ sunt traseele atunci perechea celor mai apropiate $2$ noduri o notam cu $(x, y)$, cu $x$ apartinand $[a, b]$ si $y$ apartinand $[c, d]$ atunci $(x, y)$ apartine ${ (a,c), (a,d), (b,c), (b,d)}$.

* prin notatia $[a, b]$ intelegem traseul care incepe in orasul $a$, iar ultimul sau nod parcurs este orasul $b$. Pentru oricare $2$ trasee date cele mai apropiate $2$ orase, din punct de vedere al numarului strazilor parcurse de la unul la celalalt, apartin multimii extremitatilor traseelor. (daca $[a, b]$ si $[c, d]$ sunt traseele atunci cele mai apropiate $2$ noduri, fie aceastea $x$ si $y$ apartin multimii ${ a, b, c, d}$.

h2. Date de intrare