F. Медведь и химия
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Умный бурый мишка Лимак обожает химию, особенно ему нравятся химические реакции превращения элементов друг в друга.

В Беарляндии (родине Лимака) есть n химических элементов, пронумерованных от 1 до n. Также там существуют специальные машины, которые превращают элементы друг в друга. Каждая машина описывается парой чисел ai и bi (не обязательно различных), означающей что машина может превратить элемент ai в bi и наоборот, превратить элемент bi в ai. Машины в Беарляндии очень ненадёжные и каждая из них может быть использована не более одного раза. Допустимо, что ai = bi или несколько машин преобразуют одну и ту же пару ai и bi.

Радевуш — главный соперник Лимака, и он решил проверить его знание химии. Завтра они встретятся, и каждый принесёт с собой все имеющиеся у него машины. У Лимака есть m машин, но о машинах Радевуша он ничего не знает. Оно договорились, что Радевуш выберет два различных элемента x и y. Лимак начинает с элемента x и должен перевести его в элемент y используя имеющиеся машины, а затем перевести элемент обратно в x. Для выполнения задачи Лимак может использовать как свои машины, так и машины Радевуша, но каждую машину можно применить не более одного раза.

Известно, что у Радевуша есть непустое множество любимых элементов, и он обязательно выберет x и y из этого множества. Лимак не знает ни элементов в этом множестве, ни какие машины есть у Радевуша, но до него дошли q слухов, каждый из которых содержит описание машин Радевуша и его любимого множества.

Теперь для каждого слуха Лимак хочет знать, правда ли, что используя свои машины и машины Радевуша (согласно слуху) он сможет успешно выполнить преобразование для любой пары различных элементов x и y из множества любимых элементов Радевуша (опять же, согласно слуху).

Входные данные

В первой строке входных данных записаны три числа n, m и q (1 ≤ n, q ≤ 300 000, 0 ≤ m ≤ 300 000) — количество элементов, количество машин Лимака и количество слухов соответственно.

В каждой из последующих m строк записаны два числа ai и bi (1 ≤ ai, bi ≤ n), описывающие i-ю машину Лимака.

Затем следует q описаний слухов.

В первой строке каждого описания i-го слуха записаны два числа ni и mi (1 ≤ ni ≤ 300 000, 0 ≤ mi ≤ 300 000). Во второй строке описания записы ni различных чисел xi, 1, xi, 2, ..., xi, ni (1 ≤ xi, j ≤ n) — любимые элементы Радевуша согласно данному слуху. Обратите внимание, что если ni = 1, то Лимак автоматически выигрывает, поскольку нельзя выбрать ни одной пары различных x и y (и ответ «YES»). В следующих mi строках записаны по два числа ai, j, bi, j (1 ≤ ai, j, bi, j), описывающие Машины Радевуша в i-м слухе.

Гарантируется, что сумма всех ni не превосходит 300 000. Аналогично, сумма всех mi тоже не превосходит 300 000.

Важно! Поскольку мы хотели бы, чтобы вы обрабатывали слухи один за другим, получить очередной запрос можно только узнав ответ на предыдущий. Для этого необходимо ко всем числам, описывающим множество любимых элементов Радевуша и его машины применить следующую функцию:

int rotate(int element)
{
   element=(element+R)%n;

   if (element==0) {
       element=n;
   }

   return element;
}

Здесь R изначально равняется 0 и увеличивается на порядковый номер запроса каждый раз, когда ответом является «YES». Запросы нумеруются начиная с 1 в порядке, в котором они встречаются во входных данных.

Выходные данные

Выведите q строк, для i-го запроса выведите «YES» (без кавычек), если для i-го слуха Лимак сумеет успешно перевести друг в друга любую пару элементов x и y из множества xi, 1, xi, 2, ..., xi, ni. В противном случае выведите «NO».

Примеры
Входные данные
6 5 4
1 2
2 3
3 4
2 4
5 6
2 0
4 2
2 1
6 2
3 4
3 2
6 3 4
2 5
4 6
2 1
1 2
1 2
Выходные данные
YES
NO
YES
YES
Входные данные
7 6 2
1 2
1 3
2 4
2 5
3 6
3 7
7 2
1 2 3 4 5 6 7
4 5
6 7
7 2
1 2 3 4 5 6 7
4 6
5 7
Выходные данные
NO
YES
Примечание

Рассмотрим первый пример.

В первом слухе любимым множеством Радевуша является {4, 2} и у него нет машин. Лимак может преобразовать элемент 4 в элемент 2, а затем 2 в 3 и 3 в 4. Таким образом, ответ «YES» и R увеличивается на 1.

Во втором слухе задач набор {6, 2} и машина (3, 4), но поскольку R = 1, то реально требуется рассмотреть множество {1, 3} и машину (4, 5). Ответ «NO» и значение R не меняется.

В третьем слухе множество {6, 4, 3} и машины (2, 5) и (4, 6) переводятся в {1, 5, 4}, (3, 6) и (5, 1)

Рассмотрим возможный выбор Радевуша:

  • Если выбрать элементы 1 и 5, то Лимак может перевести 1 в 5, затем 6 в 3, 3 в 2 и, наконец, 2 в 1.
  • Если он выберет элементы 5 и 4, то Лимак может перевести 5 в 6, 6 в 3, 3 в 4, а затем 4 в 2, 2 в 1, 1 в 5.
  • Наконец, если выбрать элементы 1 и 4, то Лимак может превратить 1 в 2, потом 2 в 4, 4 в 3, 3 в 6, 6 в 5 и 5 в 1.

Таким образом Лимак может выполнить задачу для любой пары x и y и ответ «YES», а значение R увеличивается на 3 и становится равно 4.

В последнем слухе {1, 2} и (1, 2) переводятся в {5, 6} и (5, 6). Имеются две машины (5, 6) и Лимак легко справляется с заданием.