POLSKI SPOJ

W niedalekiej przyszłości Bajtocka Agencja Kosmiczna (BAK) wyśle na najbliższą planetę, na której jest życie, oddaloną o zaledwie kilka milionów lat świetlnych, statek kosmiczny. Celem wyprawy jest kolonizajca tej planety. Już prawie wszystko gotowe. Został tylko do napisania program, który w razie awarii poprowadzi załogę do bezpiecznej części statku, która jest niezależna i jest w stanie oddzielić się od statku kosmicznego i bezpiecznie dotrzeć do najbliższej stacji kosmicznej ratując w ten sposób załogę. Takich elementów statku może być kilka. Oto kilka zasad poruszania się w czasie awarii:

• podłączenie A  B oznacza, że element statku A jest podłączony do elementu B i można przemieścić się tylko w kierunku z pomieszczenia (elementu) A do B
• każde pomieszczenie składa się z wejść i wyjść. Oznacza to, że nie można go opuścić wejściem oraz wejść do niego wyjściem
• statek można opuścić z niezależnej części statku tylko wtedy, gdy nie jest ona podłączona do żadnego innego elementu oraz żaden element nie jest do niej podłączony
• załoga przechodzi z pomieszczenia A do pomieszczenia B tylko wtedy, gdy istenieje bezpośrednie wyjście z pomieszczenia A do B. Następnie element A może być odłączony tylko wtedy, gdy zostały odłączone wszystkie elementy podłączone do elementu A
• odłączenie elementu A od B można wykonać tylko w sytuacji, gdy prześliśmy bezpośrednio z A do B
• jeżeli jest kilka wyjść z pomieszczenia A, a wszystkie elementy zostały już od niego odłączone lub do pomieszczenia A nie prowadzi zadne wejście, to aby odłączyć element A, załoga musi się rozdzielić wchodząc bezpośrednio do wszystkich elementów statku, do których jest wyjście z A i równocześnie odłączyć element A.
• załoga uratuje się, jeśli każdy znajdzie się w pomieszczeniu do którego nie jest podłączony żaden element oraz pomieszczenie to nie jest podłączone do żadnego innego

Wejście

W pierwszym wierszu jedna niewielka liczba określająca liczbę zestawów danych. Specyfikacja zestawu:

W pierwszym wierszu liczba n określająca liczbę elenemtów (pomieszczeń) statku (nie więcej niż 1000) oraz jedna liczba m określająca liczbę połączeń między elementami statku (nie więcej niż 5000).

W kolejnych m wierszach po dwie liczby a i b przedstawiające informację, że z pomieszczenia o numerze a można przedostać się do pomieszczenia o numerze b.

W ostatnim wierszu każdego zestawu jedna liczba określająca numer pomieszczenia, w którym początkowo znajduje się załoga. Można założyć, że to pomieszczenie posiada tylko wyjścia.

Wyjście

Dla każdego zestawu w osobnym wierszu napis TAK jeśli załoga może się uratować lub napis NIE w przeciwnym razie.

Wejście

Wejście:
1
5 6
1 2
2 4
2 3
3 4
3 5
5 4
1

Wyjście:
TAK