题目背景

:::align{center} :::

题目描述

有 $N$ 个海狸城镇，按高度从高到低编号为 $1$ 至 $N$。任意两个城镇的高度均不相同。有 $M$ 条单向运河连接两个不同的城镇。第 $i$ 条运河（$1 \le i \le M$）从城镇 $S_i$ 流向城镇 $E_i$。这些运河均从高处城镇流向低处城镇，你不能逆着水流方向移动。

海狸 Bitaro 有 $N$ 个朋友，每个朋友分别居住在 $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$，表示第 $i$ 条运河从 $S_i$ 单向流向 $E_i$。
• 接下来的 $Q$ 行中，第 $j$ 行（$1 \le j \le Q$）包含两个以空格分隔的整数 $T_j$、$Y_j$，以及 $Y_j$ 个以空格分隔的整数 $C_{j,1}, C_{j,2}, \ldots, C_{j,Y_j}$。这表示第 $j$ 场派对在城镇 $T_j$ 举行，且居住在城镇 $C_{j,1}, C_{j,2}, \ldots, C_{j,Y_j}$ 的朋友因忙碌而无法参加。

输出格式

输出包含 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）包含第 $j$ 场派对中，使用最多运河路径的参与者所经过的运河数量。若无人能参加第 $j$ 场派对，则第 $j$ 行输出 $-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
3
0

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

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

提示

样例 1 解释

在参加第一场派对的朋友中（居住在城镇 $2$、$3$ 或 $4$ 的朋友），居住在城镇 $2$ 或 $3$ 的朋友会通过最多数量的运河前往派对所在的城镇 $4$，该数量为 $1$，因此输出 $1$。

在参加第二场派对的朋友中（居住在城镇 $1$、$4$ 或 $5$ 的朋友），居住在城镇 $1$ 的朋友会通过最多数量的运河前往派对所在的城镇 $5$，该数量为 $3$，因此输出 $3$。

居住在城镇 $2$ 的朋友是唯一参加第三场派对的人，他不经过任何运河，因此输出 $0$。

数据范围

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

• $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) \ne (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} < \cdots < C_{j,Y_j} \le N$（其中 $1 \le j \le Q$）。
• $Y_1 + Y_2 + \cdots + Y_Q \le 100\,000$。

子任务

共有 3 个子任务。每个子任务的得分及附加约束如下：

子任务 1 [7 分]

• $N \le 1000$。
• $M \le 2000$。
• $Q = 1$。

子任务 2 [7 分]

• $Q = 1$。

子任务 3 [86 分]

无额外约束。