Ski Resort

You own a well-known ski resort in the US, and you would like to increase your sales by stocking the snack stands at good locations across the resort.

The ski resort is built on a mountain. A ski lift takes a guest to the top of the mountain. From there, the guest can ski to a number of locations on the mountain.

There are $n$ areas on the mountain, labeled $1$ to $n$. The top of the mountain is area $1$. Areas are connected by ski runs that are strictly downhill. In other words, after leaving an area, a guest cannot return to it without taking the ski lift. Every area (including area $1$) has exactly one snack stand.

As the owner of the resort, you want to know how effectively you can distribute snacks among the snack stands to serve your guests better (and make more money). To this end, you run a survey and analyze the results with a number of independent queries. Each guest in the survey has a favorite snack and a list of favorite areas that they like to visit. You would like to know how best to stock your snack stands with their favorite snack.

Each query is a set of one guest's favorite areas and a number $k$. Count the ways to stock this guest's favorite snack at exactly $k$ snack stands on the mountain so that the following conditions hold:

1. For each of this guest's favorite areas, over all sequences of ski runs that reach that area from the top of the mountain, there must be exactly one snack stand with the guest's favorite snack. In other words, the guest must not have a choice of more than one snack stand where the snack is available. So among the areas that lie on at least one route from area $1$ to that area (both ends included), exactly one has a stocked stand, and every route from area $1$ to that area passes through it.
2. Each of the $k$ snack stands stocked with this guest's favorite snack must lie on some sequence of ski runs from the top of the mountain to some area in the query set.

The input consists of a single test case. Your program may be run multiple times on different inputs.

The first line contains three space-separated integers $n$, $m$, and $q$, where $n$ ($1 \le n \le 10^5$) is the number of areas on the mountain, $m$ ($1 \le m \le n + 50$) is the number of runs, and $q$ ($1 \le q \le 10^5$) is the number of queries.

Each of the next $m$ lines contains two integers $x$ and $y$ ($1 \le x, y \le n$, $x \ne y$), meaning there is a ski run from area $x$ down to area $y$. There is at most one run between any two areas. Every area can be reached from area $1$ by some chain of ski runs.

Each of the next $q$ lines is a sequence of space-separated integers that starts with $k$ and $a$ and continues with $a$ integers $i$. Here $k$ ($1 \le k \le 4$) is the number of snack stands to stock with this guest's favorite snack, $a$ ($1 \le a \le n$) is the number of areas in the query set, and the $a$ integers $i$ ($1 \le i \le n$) are the labels of the areas in the query set. Within a query, no integer $i$ is repeated.

The sum of all $a$ over all queries does not exceed $100\,000$.

Print $q$ integers, each on its own line, with no blank lines in between. Each integer is the number of ways to choose the snack stands to stock for the corresponding query, in the order the queries appear in the input. Two ways are different if an area is selected in one of them but not in the other.