Вы — предприимчивый владелец всемирно известного горнолыжного курорта в США и хотите увеличить продажи, снабдив закусочные в ключевых местах своих владений.

Курорт расположен на горе. Подъёмник может доставить посетителя на вершину, откуда он может спуститься на лыжах в различные места на горе.

На горе есть $n$ зон, пронумерованных от $1$ до $n$. Вершина горы — зона $1$. Зоны соединены лыжными трассами, ведущими строго вниз. Иными словами, покинув зону, невозможно вернуться в неё без использования подъёмника. В каждой зоне (включая зону $1$) находится ровно одна закусочная.

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

Каждый запрос состоит из множества любимых зон посетителя и числа $k$. Вы хотите узнать, сколькими способами можно распределить любимую закуску этого посетителя ровно по $k$ закусочным на горе так, чтобы выполнялись следующие условия:

1. Для каждой любимой зоны этого посетителя среди всех последовательностей лыжных трасс, ведущих от вершины горы в эту зону, должна быть ровно одна закусочная с его любимой закуской. (Иными словами, у него не должно быть выбора из нескольких закусочных, в которых доступна его закуска.)
2. Каждая из $k$ закусочных, снабжённых любимой закуской этого посетителя, должна находиться на некоторой последовательности лыжных трасс от вершины горы до некоторой зоны из множества запроса.

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

Каждый входной файл содержит один тест. Обратите внимание, что ваша программа может запускаться несколько раз на разных входных данных. Первая строка содержит три целых числа $n$, $m$ и $q$, разделённых пробелами, где $n$ ($1 \le n \le 10^5$) — количество зон на горе, $m$ ($1 \le m \le n+50$) — количество трасс, а $q$ ($1 \le q \le 10^5$) — количество запросов.

Каждая из следующих $m$ строк содержит два целых числа $x$ и $y$ ($1 \le x,y \le n$, $x \ne y$), обозначающих лыжную трассу из зоны $x$ в зону $y$. Между любыми двумя зонами существует не более одной трассы. Из зоны $1$ можно добраться до каждой зоны по некоторой цепочке лыжных трасс.

Каждая из следующих $q$ строк представляет собой последовательность целых чисел, разделённых пробелами: сначала идут $k$ и $a$, за которыми следуют $a$ целых чисел $i$. Здесь $k$ ($1 \le k \le 4$) — количество закусочных, которые нужно снабдить любимой закуской этого посетителя, $a$ ($1 \le a \le n$) — количество зон в множестве запроса, а $a$ целых чисел $i$ ($1 \le i \le n$) — номера зон в этом множестве. В пределах одного запроса никакое число $i$ не повторяется.

Сумма всех $a$ по всем запросам не превосходит $100\,000$.

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

Выведите $q$ целых чисел, каждое в отдельной строке, без пустых строк между ними. Они обозначают количество способов выбрать закусочные для снабжения в каждом запросе в порядке их появления во входных данных. Два способа считаются различными, если какая-либо зона выбрана в одном из них и не выбрана в другом.

Примеры

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

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

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

2
0
2
1

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

8 10 4
1 2
2 3
1 3
3 6
6 8
2 4
2 5
4 7
5 7
7 8
2 3 4 5 6
2 2 6 8
1 1 6
1 1 8

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

0
0
3
2

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

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

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

2
0
3
2