시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

Bajtazar przygotowuje się, aby zmienić stan cywilny. Ma on wiernych kumpli, którzy postarają się, aby ostatnie dni stanu wolnego były niezapomniane. Dla niego i połowy Bajtocji. W Bajtocji (jak zapewne pamiętacie) jest n miast, ponumerowanych od 0 do n - 1. Niektóre pary miast łączy dwukierunkowa droga, niemniej jednak większość dróg jest aktualnie w remoncie. Pozostało tylko tyle, aby z każdego miasta można było dojechać do każdego innego na dokładnie jeden sposób. Przewidujący kumple Bajtazara zaopatrzyli się w p biletów lotniczych. Każdy bilet pozwala na jeden przelot, w dowolnym momencie, z pewnego miasta a do miasta b (ale nie w drugą stronę). Bajtazar chciałby zacząć podróż w ustalonym mieście s i skończyć ją w ustalonym mieście t. Będzie używał (niektórych) dróg oraz połączeń lotniczych, przy czym chciałby wykorzystać wszystkie swoje bilety, w dowolnej kolejności. Niestety, z pewnych zrozumiałych względów, po tym jak opuści pewne miasto, więcej nie będzie mógł się tam pojawić. Twoim zadaniem będzie odpowiedzieć na pytanie, czy trasa spełniająca powyższe warunki istnieje.

입력

W pierwszym wierszu standardowego wejścia znajduje się liczba testów T. Dalej następuje T testów, w następującej postaci: Pierwszy wiersz testu zawiera trzy liczby całkowite n, m oraz p (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 1 000 000, 1 ≤ p ≤ 1 000 000), oznaczające liczbę miast w Bajtocji, liczbę czynnych dróg oraz liczbę biletów lotniczych, które posiada Bajtazar. W drugim wierszu testu znajdują się dwie liczby całkowite s i t (0 ≤ s, tn - 1) oznaczające miasto początkowe i końcowe.

Kolejne m wierszy zawiera opisy bajtockich dróg, po jednej w wierszu. Każdy opis składa się z dwóch liczb całkowitych aibi (0 ≤ ai, bin - 1, aibi), oznaczających, że i-ta droga łączy miasta ai oraz bi. Kolejne p wierszy to opisy możliwych przelotów Bajtazara. Każdy opis składa się z dwóch liczb całkowitych cidi (0 ≤ ci, din - 1, cidi). Oznacza on, że Bajtazar jest w posiadaniu biletu z miasta ci do di.

출력

Twój program powinien wypisać na standardowe wyjście, dla każdego testu, słowo TAK lub NIE w osobnym wierszu. TAK oznacza, że da się wytyczyć pożądaną przez Bajtazara trasę, NIE — że jest to niemożliwe.

예제 입력 1

2
3 2 1
1 0
0 1
0 2
1 2
3 2 1
1 0
0 1
0 2
2 1

예제 출력 1

TAK
NIE