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 date cele mai apropiate $2$ orase, din punct de vedere al numarului strazilor parcurse de la unul la celalalt, apartin multimii extremitatilor traseelor. (daca avem traseele $[a, b]$ si $[c, d]$ atunci cele mai apropiate $2$ noduri ale lor, fie aceastea $x$ si $y$, apartin multimii ${ a, b, c, 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