H - Obcy

Zostałeś zatrudniony przez super tajną agencję rządową. Dosłownie przed chwilą agenci specjalni złapali pozaziemską istotę myślącą, i teraz przetrzymują ją w ściśle tajnym kompleksie badawczym, gdzie przedstawiciele różnych dziedzin wiedzy mogą przeprowadzać swoje doświadczenia. Oczywiście nie wszyscy naukowcy są na tyle godni zaufania aby ich dopuścić do tak wielkiej tajemnicy. Dlatego też tylko osoby z przepustką 5-tego stopnia powinni być wpuszczani na teren nowego "domu" obcego. Reszta ludzi powinna mieć możliwość w miarę swobodnego poruszania się po pozostałych pomieszczeniach kompleksu. Pomieszczenia są ze sobą połączone za pomocą jednokierunkowych śluz powietrznych, tak że poruszać można się nimi tylko w jedną stronę.

Aby chronić cennego obcego musisz ustawić strażnika w jednym z pomieszczeń kompleksu badawczego tak aby wszystkie drogi od wejścia do obcego były przez niego kontrolowane. Jednak strażnik nie jest na tyle wtajemniczony aby wiedzieć o obcym, więc nie może znajdować się z nim w jednym pomieszczeniu. Strażnik będzie sprawdzać wszystkich. Dlatego też, w celu zmniejszenia rozdrażnienia naukowców nie posiadających 5-tego stopnia wtajemniczenia, musisz go tak umieścić aby blokował jak najmniej innych pomieszczeń. Mówiąc ściślej, pomieszczenie gdzie będzie stacjonować strażnik powinno posiadać następujące cechy:

1. Chcąc dojść do laboratorium z obcym trzeba przejść przez pokój ze strażnikiem.
2. Strażnik nie może znajdować się w pomieszczeniu z obcym.
3. Nie ma żadnego pokoju o cechach 1 i 2 bliższego pomieszczeniu z obcym.

Warto zauważyć, że pomieszczenie 2 spełnia pierwsze dwa warunki, jednakże 3 znajduje się bliżej obcego, dlatego też tam trzeba umieścić strażnika.

Wejście

Pierwsza linia wejścia zawiera liczbę zestawów testowych D. Następnie, w każdym zestawie, pierwsza linia zawiera 3 liczby całkowite N, K i E (2≤N≤200, 1≤K≤N*(N–1), 0<E<N), oznaczające odpowiednio liczbę wierzchołków, liczbę krawędzi oraz miejsce przetrzymywania obcego. Następne K linii zestawu testowego zajmuje spis śluz w postaci: źródło cel (nie istnieją dwie śluzy łączące tę samą parę komnat, w tym samym kierunku). Należy zauważyć, że pomieszczenia są numerowane od 0. Wejście do kompleksu jest zawsze przez pomieszczenie 0. Można założyć, że z wejścia da się na pewno dość do pomieszczenia z obcym.

Wyjście

Dla każdego zestawu testowego powinna zostać wypisana pojedyncza liczba określająca miejsce ustawienia strażnika.

Przykładowe wejście

2
4 6 3
0 1
0 2
1 2
2 1
1 3
2 3
9 13 4
0 2
2 3
3 4
5 3
5 4
3 6
6 5
6 7
6 8
4 7
0 1
1 7
7 0


Przykładowe wyjście

0
3