Zadanie PPR8

Treść

Dany jest graf oraz dwa jego wierzchołki. Stwierdź, czy istnieje ścieżka łacząca te dwa wierzchołki w grafie.

Specyfikacja wejścia

Pierwsza linia wejścia zawiera liczbę całkowitą D (1 <= D <= 50), oznaczają liczbę zestawów danych. W pierwszej linii zestawu znajdują się dwie liczby naturalne n i m (1<=n<=5000, 0<=m<= 50000) oznaczające odpowiednio liczbę wierzchołków oraz liczbę krawędzi w grafie. Kolajnych m linii zawiera pary liczb z przedziału od 1 do n, które oznaczają krawędzie znajdujące się w grafie. W ostatniej linii zestawu znajdują się dwie liczby naturalne x i y (1<=x,y<=n) oznaczające numery wierzchołków pomiędzy którymi szukać będziemy połączenia.

Specyfikacja wyjścia

Na wyjściu należy dla każdego zestawu danych wypisać w osobnej linii "TAK", jeśli istnieje połączenie między wierzchołkami, lub "NIE" jeśli połączenie takie nie istnieje.

Przykład

Wejście

2
3 3
1 2
2 3
3 1
1 2
7 9
1 2
2 3
3 4
4 1
1 3
2 4
6 7
7 5
6 5
1 5

Wyjście

TAK
NIE