Runda 3: Sieci wifi

Limit czasowy: 3 sekundy
Limit pamięciowy: 32 MB

Ojciec Jasia dostał pracę jako administrator sieci w pewnej firmie. W jego firmowej sieci komputery są połączone za pomocą połączeń kablowych, ale dodatkowo niektóre z komputerów są wyposażone w interfejs do komunikacji bezprzewodowej. Dwa komputery w takiej sieci mogą się komunikować bezpośrednio jeżeli są połączone bezpośrednim połączeniem kablowym, albo oba są wyposażone w interfejs bezprzewodowy. Komputer A w takiej sieci może się komunikować z dowolnym innym komputerem B jeżeli istnieje ciąg komputerów, w którym kolejne dwa mogą się komunikować bezpośrednio, oraz pierwszy komuter w ciągu to komputer A, ostatni natomiast to komputer B. Na początku w sieci możliwa jest komunikacja między każdymi dwoma komputerami bez potrzeby wykorzystania interfejsów bezprzewodowych.

Niestety w dużych sieciach komutery ulegają awariom, co może spowodować brak łączności pomiędzy pewnymi komputerami. Ojciec Jasia, chcąc minimalizować ryzyko braku łączności chciałby wiedzieć, czy mimo zepsucia jednego komputera nadal będzie możliwa komunikacja między każdymi dwoma komputerami. Twoim zadaniem jest pomóc ojcu Jasia. Napisz dla niego program, który wczyta opis sieci oraz numery komputerów wyposażonych w interfejs bezprzewodowy, i odpowie TAK jeżeli mimo zepsucia dowolnego, ale w danym czasie tylko jednego komputera będzie możliwa komunikacja między dowolnymi dwomia komputerami, oraz NIE w przeciwnym przypadku.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba naturalna T (1<=T<=10) oznaczająca ilość zestawów testowych. W pierwszej linii każdego zestawu znajdują się dwie liczby naturalne N, M (1<=N<=10000, 1<=M<=1000000), oznaczające odpowiednio ilość komputerów w sieci, oraz ilość połączeń kablowych. W kolejnych M liniach znajdują się po dwie liczby naturalne A, B (1<=A,B<=N), oznaczające bezpośrednie połączenie między komputerami o numerach A i B. W kolejnej linii wejścia znajduje się jedna liczba naturalna K (0<=K<=N), oznaczająca liczbę komputerów wyposażonych w interfejs bezprzewodowy. W następnych K liniach znajduje się po jednej liczbie naturalnej C (1<=C<=N). Są to numery komputerów wyposażonych w interfejs bezprzewodowy (żadna liczba nie wystąpi tutaj dwa razy).

Wyjście

Dla każdego pojedynczego zestawu testowego należy wypisać jedną linię zawierająca pojedyncze słowo TAK, jeżeli w danej sieci mimo zepsucia jednego z komputerów, nadal możliwa jest komunikacja między dowolnymi dwoma innymi komputerami. Lub słowo NIE w przeciwnym przypadku.

Przykład

Dla danych wejściowych:

2
3 2
1 2
2 3
2
1
3
5 5
1 2
2 3
3 4
4 1
1 5
1
3

poprawną odpowiedzią jest:

TAK
NIE