En tant que propriétaire entreprenant d'une station de ski américaine de renommée mondiale, vous aimeriez augmenter vos ventes en approvisionnant des stands de collations à des endroits clés de votre domaine.

La station est construite sur une montagne. Une remontée mécanique peut conduire un visiteur au sommet. De là, il peut skier vers plusieurs endroits de la montagne.

La montagne comporte $n$ zones, numérotées de $1$ à $n$. Le sommet est la zone $1$. Les zones sont reliées par des pistes strictement descendantes. Autrement dit, après avoir quitté une zone, il est impossible d'y revenir sans emprunter la remontée mécanique. Chaque zone (y compris la zone $1$) possède exactement un stand de collations.

En tant que propriétaire, vous voulez savoir comment répartir efficacement les collations entre les stands pour mieux servir vos visiteurs (et gagner davantage d'argent). Vous souhaitez donc réaliser une enquête et en analyser les résultats au moyen de plusieurs requêtes indépendantes. Chaque visiteur interrogé a une collation favorite et une liste de zones favorites qu'il aime visiter. Vous aimeriez savoir comment approvisionner au mieux vos stands avec sa collation favorite.

Chaque requête consiste en un ensemble de zones favorites d'un visiteur et un nombre $k$. Vous voulez connaître le nombre de façons de distribuer sa collation favorite à exactement $k$ stands de la montagne, en respectant les conditions suivantes :

1. Pour chacune de ses zones favorites, sur l'ensemble de toutes les suites de pistes permettant de l'atteindre depuis le sommet, il doit exister exactement un stand proposant sa collation favorite. (Autrement dit, il ne doit pas avoir le choix entre plusieurs stands où cette collation est disponible.)
2. Chacun des $k$ stands approvisionnés avec sa collation favorite doit appartenir à une suite de pistes allant du sommet à une zone de l'ensemble de la requête.

Entrée

Chaque entrée contient un seul cas de test. Notez que votre programme peut être exécuté plusieurs fois sur des entrées différentes. La première ligne contient trois entiers séparés par des espaces, $n$, $m$ et $q$, où $n$ ($1 \le n \le 10^5$) est le nombre de zones, $m$ ($1 \le m \le n+50$) le nombre de pistes et $q$ ($1 \le q \le 10^5$) le nombre de requêtes.

Les $m$ lignes suivantes contiennent chacune deux entiers $x$ et $y$ ($1 \le x,y \le n$, $x \ne y$), représentant une piste allant de la zone $x$ à la zone $y$. Il existe au plus une piste entre deux zones quelconques. Chaque zone est accessible depuis la zone $1$ par une suite de pistes.

Chacune des $q$ lignes suivantes est une suite d'entiers séparés par des espaces, commençant par $k$ et $a$, suivis de $a$ entiers $i$. Ici, $k$ ($1 \le k \le 4$) représente le nombre de stands à approvisionner avec la collation favorite de ce visiteur, $a$ ($1 \le a \le n$) le nombre de zones de l'ensemble de la requête, et les $a$ entiers $i$ ($1 \le i \le n$) sont les numéros de ces zones. Dans une même requête, aucun entier $i$ n'est répété.

La somme des $a$ sur toutes les requêtes ne dépasse pas $100\,000$.

Sortie

Affichez $q$ entiers, chacun sur sa propre ligne, sans ligne vide entre eux. Ils représentent le nombre de façons de choisir les stands à approvisionner pour chaque requête, dans l'ordre de l'entrée. Deux façons sont considérées comme différentes si une zone est sélectionnée dans l'une et pas dans l'autre.

Exemples

Entrée 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

Sortie 1

2
0
2
1

Entrée 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

Sortie 2

0
0
3
2

Entrée 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

Sortie 3

2
0
3
2