LibreOJ

2838 「JOISC 2018 Day 3」比太郎的聚会

内存限制：512 MB 时间限制：2000 ms

题目描述

译自 JOISC 2018 Day3 T2「ビ太郎のパーティー / Bitaro's Party」

bitaro.png

河狸们有 $N$ 个城镇，这些城镇按照海拔从高到低依次编号为 $1\ldots N$（保证海拔互不相同）。有 $M$ 条运河，$i$ 号运河从城镇 $S_i$ 流向 $E_i$。所有的运河都从海拔高的地方流向海拔低的地方。河狸们不能沿着运河逆流而上，即：河狸不能从城镇 $E_i$ 通过 $i$ 号运河前往城镇 $S_i$。

河狸比太郎有在每个城镇各有一位朋友。比太郎打算举办 $Q$ 场聚会。第 $j$ 场聚会在城镇 $T_j$ 进行，已知有 $Y_j$ 名河狸因事无法参加。在剩下的河狸中，除非他无法从他所在的城镇到达 $T_j$，否则他一定会来。

因为河狸们十分喜欢运河，所以他们会沿经过运河数目最多的一条路径参加聚会，比太郎想知道每次聚会经过运河数目最多的河狸会经过多少条运河。

任务

给定 $Q$ 场聚会举行的城镇编号和因事无法参加的河狸列表，写一个程序求出参加每次聚会经过运河数目最多的河狸会经过多少条运河。

输入格式

从标准输入中读入如下内容： - 输入的第一行包含三个用空格隔开的整数 $N,M,Q$，表示有 $N$ 个河狸城镇，$M$ 条运河，要举行 $Q$ 场聚会； - 接下来 $M$ 行，第 $i$ 行有两个用空格隔开的整数 $S_i,E_i$，表示运河单向地从 $S_i$ 流向 $E_i$； - 接下来 $Q$ 行，第 $j$ 行包含一些整数，前两个用空格分开的整数 $T_j,Y_j$，后面有 $Y_j$ 个用空格隔开的整数 $C_{j,1},C_{j,2},\cdots ,C_{j,Y_j}$，表示第 $j$ 场聚会在 $T_j$ 镇举行，住在 $C_{j,1},C_{j,2},\cdots ,C_{j,Y_j}$ 的河狸因事不能来参加聚会。

输出格式

输出 $Q$ 行，第 $j$ 行包含一个整数，表示参加每次聚会经过运河数目最多的河狸会经过多少条运河。如果没有河狸能参加这场聚会，输出 $-1$。

样例 1

在参加第 $1$ 场聚会的朋友中（住在 $2,3,4$ 号城镇的河狸），在 $2$ 或 $3$ 号城镇的河狸会沿运河前往 $4$ 号城镇，他们都将经过 $1$ 条运河，所以输出 $1$。 在参加第 $2$ 场聚会的朋友中（住在 $1,4,5$ 号城镇的河狸），在 $1$ 号城镇的河狸会沿运河前往 $5$ 号城镇，将经过 $3$ 条运河，所以输出 $3$。 在参加第 $3$ 场聚会的朋友中（住在 $2$ 号城镇的河狸），他没有经过运河到达 $2$ 号城镇，因此输出 $0$。

样例 2

数据范围与提示

对于全部数据，满足以下条件： - $1\le N\le 10^5$ - $0\le M\le 2\times 10^5$ - $1\le Q\le 10^5$ - $1\le S_i\lt E_i\le N\ (1\le i\le N)$ - $(S_i,E_i)\neq (S_j,E_j)\ (1\le 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}\lt C_{j,2}\lt \cdots \lt C_{j,Y_j}\le N\ (1\le j\le Q)$ - $Y_1+Y_2+\cdots Y_Q\le 10^5$

本题包含三个子任务，具体子任务限制如下：

Subtask 附加限制 分数
$1$ $N\le 10^3,M\le 2\times 10^3,Q=1$ $7$
$2$ $Q=1$ $7$
$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

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