有 $N$ 个海狸城镇，编号从 $1$ 到 $N$，按海拔高度降序排列。没有两个城镇的海拔高度相同。有 $M$ 条单向运河连接两个不同的城镇。第 $i$ 条运河 ($1 \le i \le M$) 从城镇 $S_i$ 流向城镇 $E_i$。这些运河从高海拔城镇流向低海拔城镇。你不能逆着运河的水流方向移动。

海狸 Bitaro 有 $N$ 个朋友，每个城镇住着其中一个朋友。

Bitaro 将举办 $Q$ 次聚会来邀请他的朋友。已知对于第 $j$ 次聚会 ($1 \le j \le Q$)，有 $Y_j$ 个朋友因为太忙而无法参加。第 $j$ 次聚会将在城镇 $T_j$ 举行，因此那些无法仅通过运河从他们所在的城镇到达城镇 $T_j$ 的朋友也无法参加。其他朋友会来参加聚会。

每个朋友通过运河来到举办聚会的城镇。他们可以选择多条路径。但是 Bitaro 的朋友们热爱运河，所以他们必须选择其中一条包含运河数量最多的路径。

Bitaro 想知道，在参加聚会的人中，使用运河数量最多的那个人所经过的运河数量是多少。

题目描述

给定举办聚会的城镇索引以及 $Q$ 次聚会中忙碌的朋友列表，编写一个程序，计算参加聚会的人中，使用运河数量最多的那个人所经过的运河数量。

输入格式

从标准输入读取以下数据。

• 第一行包含三个空格分隔的整数 $N, M, Q$。这意味着有 $N$ 个海狸城镇，$M$ 条运河，以及 Bitaro 要举办的 $Q$ 次聚会。
• 接下来的 $M$ 行中，第 $i$ 行 ($1 \le i \le M$) 包含两个空格分隔的整数 $S_i$ 和 $E_i$。这意味着运河从 $S_i$ 单向流向 $E_i$。
• 接下来的 $Q$ 行中，第 $j$ 行 ($1 \le j \le Q$) 包含两个空格分隔的整数 $T_j, Y_j$，以及 $Y_j$ 个空格分隔的整数 $C_{j,1}, C_{j,2}, \dots, C_{j,Y_j}$。这意味着第 $j$ 次聚会在城镇 $T_j$ 举行，且居住在城镇 $C_{j,1}, C_{j,2}, \dots, C_{j,Y_j}$ 的朋友很忙。

输出格式

输出包含 $Q$ 行。第 $j$ 行 ($1 \le j \le Q$) 包含第 $j$ 次聚会中，使用运河数量最多的参加者所经过的运河数量。如果没有人能参加第 $j$ 次聚会，则第 $j$ 行输出 -1。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 100\,000$
• $0 \le M \le 200\,000$
• $1 \le Q \le 100\,000$
• $1 \le S_i < E_i \le N$ ($1 \le i \le M$)
• $(S_i, E_i) \neq (S_j, E_j)$ ($1 \le i < j \le M$)
• $1 \le T_j \le N$ ($1 \le j \le Q$)
• $0 \le Y_j \le N$ ($1 \le j \le Q$)
• $1 \le C_{j,1} < C_{j,2} < \dots < C_{j,Y_j} \le N$ ($1 \le j \le Q$)
• $Y_1 + Y_2 + \dots + Y_Q \le 100\,000$

子任务

共有 3 个子任务。各子任务的分数和附加限制如下：

子任务 1 [7 分]

• $N \le 1\,000$
• $M \le 2\,000$
• $Q = 1$

子任务 2 [7 分]

• $Q = 1$

子任务 3 [86 分]

• 无附加限制。

样例

样例输入 1

5 6 3
1 2
2 4
3 4
1 3
3 5
4 5
4 1 1
5 2 2 3
2 3 1 4 5

样例输出 1

1
3
0

说明

在参加第一次聚会的朋友中（居住在城镇 2, 3 或 4 的朋友），居住在城镇 2 或 3 的朋友通过运河前往举办聚会的城镇 4，所经过的运河数量最多。这个数量是 1，因此输出 1。 在参加第二次聚会的朋友中（居住在城镇 1, 4 或 5 的朋友），居住在城镇 1 的朋友通过运河前往举办聚会的城镇 5，所经过的运河数量最多。这个数量是 3，因此输出 3。 居住在城镇 2 的朋友是唯一参加第三次聚会的人。他没有使用任何运河，因此输出 0。

样例输入 2

12 17 10
1 2
2 3
3 4
1 5
2 6
3 7
4 8
5 6
6 7
7 8
5 9
6 10
7 11
8 12
9 10
10 11
11 12
6 3 1 7 12
3 7 1 2 3 4 5 6 7
11 3 1 3 5
9 2 1 9
8 4 1 2 3 4
1 1 1
12 0
10 3 1 6 10
11 8 2 3 5 6 7 9 10 11
8 7 2 3 4 5 6 7 8

样例输出 2

1
-1
3
1
3
-1
5
2
4
4

Figure 1. Bitaro the Beaver