Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024

2020-2022 2023 Regulations Schedule RODO info Ranking

Problem description


K-pokrycie
(k-pokrycie)
Memory limit: 256 MB
Time limit: 10.00 s

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 [vK,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
3 3 2
1 2
2 3
3 1
1
3
TAK
NIE