Problem description
Ostatnio na zajęciach informatyki Ania zapoznała się z nowym pojęciem: K-pokryciem grafu. Dla danej liczby naturalnej K oraz danego grafu nieskierowanego mówimy, że podzbiór T wierzchołków tego grafu jest K-pokryciem wtedy, kiedy spełnione są dwa następujące warunki:
- Każda krawędź grafu jest incydentna z pewnym wierzchołkiem z T. Innymi słowy, dla każdej krawędzi (u,v) grafu zachodzi u ∈ T lub v ∈ T,
- Jeżeli wierzchołek o numerze v należy do T, to żaden z jego sąsiadów o numerach z przedziału [v−K,v+K] nie należy do T.
Ania, jak każda entuzjastka zadań algorytmicznych, ma swój ulubiony graf nieskierowany. Zaczęła się teraz zastanawiać, czy dla danego K istnieje K-pokrycie jej ulubionego grafu? Pomóż Ani rozwiązać ten problem.
Wejście
W pierwszym wierszu wejścia znajdują się trzy liczby naturalne N, M, Q oznaczające odpowiednio liczbę wierzchołków i liczbę krawędzi grafu Ani oraz liczbę zapytań. W następnych M wierszach następuje opis krawędzi grafu. Każdy wiersz składa się z dwóch liczb naturalnych u, v oznaczających, że w grafie występuje krawędź między wierzchołkami u i v. W następnych Q wierszach następują zapytania. W i-tym wierszu dana jest jedna liczba naturalna Ki.
Wyjście
Należy wypisać Q wierszy. W
i-tym wierszu należy wypisać
słowo TAK, jeżeli istnieje
Ki-pokrycie
grafu Ani, a w przeciwnym wypadku należy wypisać NIE.
Ograniczenia
1 ≤ N, M, Q, Ki ≤ 200 000, 1 ≤ u, v ≤ N.
Przykład
| Input | Output | |
|
|