作为一家美国知名滑雪度假村的进取型所有者，您希望通过在度假村各处的关键位置设置零食摊位来增加销售额。

滑雪度假村建在山上。滑雪缆车可以将客人带到山顶。从那里，他们可以滑雪前往山上的多个地点。

山上有 $n$ 个区域，编号为 $1 \dots 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 \neq 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