Faust a fost anunţat că va trebui să ia parte în următoarele zile la $T$ probe existenţiale (de interviu). Din fericire pentru acesta, s-a produs o breşă în sistemul de poştă electronică (vinovatul nu a fost găsit), în aşa fel încât Faust, într-un mod foarte convenabil, a obţinut dinainte probele pentru toate cele $T$ zile. În mod foarte curios, toate zilele conţineau probe foarte asemănătoare. Faust a observat că enunţul problemei era identic în fiecare dintre zile:

_Eşti într-un tărâm necunoscut, care are $N$ oraşe. Unele oraşe sunt sărace, altele sunt bogate, însă $K$ dintre ele conţin relicve valoroase. Ce va trebui să faci este să "restitui" toate relicvele, în numele **Ludai România**. Poţi să porneşti din orice oraş doreşti şi poţi să te opreşti în orice oraş doreşti, însă o dată ce vei intra într-un oraş, **fii sigur că nu vei mai putea ajunge vreodată înapoi (în viaţă)**. Alege-ţi calea în mod înţelept!_

_Eşti într-un tărâm necunoscut, care are $N$ oraşe. Unele oraşe sunt sărace, altele sunt bogate, însă $K$ dintre ele conţin relicve valoroase. Ce va trebui să faci este să "restitui" toate relicvele, în numele **Ludai România**. Poţi să proneşti din orice oraş doreşti şi poţi să te opreşti în orice oraş doreşti, însă o dată ce vei intra într-un oraş, **fii sigur că nu vei mai putea ajunge vreodată înapoi (în viaţă)**. Alege-ţi calea în mod înţelept!_

Alături de fiecare dintre cele $T$ enunţuri pe care Mefisto se pare că nu s-a obosit să le facă să pară câtuşi de puţin diferite, se află ataşată câte o descriere a tărâmului, relicvelor şi drumurilor directe între oraşe, într-un format identic cu cel din fişierul $pang.in$. Pentru simplitate, relicvele sunt identificate de oraşul în care se află.

* $1 ≤ K ≤ N ≤ 10^5^$
* $1 ≤ M ≤ 2*10^5^$
* Oraşele sunt numerotate de la $1$ la $N$

* Suma tuturor $N$-urilor din input nu va depăşi $10^5^$
* Suma tuturor $M$-urilor din input nu va depăşi $2*10^5^$

* Suma tuturor $N$-urilor din input $≤ 10^5^$
* Suma tuturor $M$-urilor din input $≤ 2*10^5^$

* Se garantează faptul că, o dată plecat dintr-un oraş $A$, Faust nu va mai avea nicio modalitate prin care să se poată întoarce în oraşul $A$.
h2. Exemplu