P14372 [JOISC 2018] 比太郎的聚会 / Bitaro's Party

:::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$。

### 样例 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 分]** 无额外约束。