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}$, sau invers( 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}$( prin notatia $[a, b]$ intelegem traseul care incepe in orasul $a$, iar ultimul sau nod parcurs este orasul $b$)

h2. Date de intrare

5934