5203. Egg to be got

单点时限: 3.0 sec

内存限制: 512 MB

现在是彩蛋时间!

有 $n$ 个彩蛋分布于 $k \times k$ 的网格图的端点上,每个彩蛋的坐标为 $(x_i,y_i)$ ,其中 $(1,1),(k,k)$ 两个端点上一定有一个彩蛋。

选取网格图中的 $m$ 条边将这些彩蛋相连(每条边都连接网格图中距离为 1 的两个点)。当你在网格图中行走时,你只能走向右或向上的边,即若当前你在 $(x,y)$ 点,你只能走另一个端点为 $(x+1,y)$ 或 $(x,y+1)$ 的边。从任意一个点出发一定可以到达 $(k,k)$ 点。

你会进行 $Q$ 次彩蛋游戏,每次游戏你会出现在其中一个彩蛋所在端点上,随后你可以从当前点出发,走向右或向上的边获取彩蛋,每当你到达一个点时,若这个点上彩蛋的种类与你之前获取的都不同,你可以获取它。

你随时可以回到本次游戏的出发点,走另一条路径。

数据保证从 $(1,1)$ 出发进行一次彩蛋游戏一定可以到达所有点。

每次游戏开始时,之前的游戏状态都会重置,即之前所有获得的彩蛋都会被放置回原处,你身上也不再持有彩蛋。现在请你求出,每次游戏你最多可以获取多少彩蛋。

下图为样例的彩蛋分布情况。

在这个网格图中,共有五种类型的彩蛋(分别用五种颜色表示),从 $D$ 点出发分别可以获取红色($D,J$),蓝色($H,L$),绿色($I,M$),粉色($K,N$)四种类型的彩蛋,因此从 $D$ 点开始进行的彩蛋游戏答案为 4。

输入格式

第一行三个整数 $n,m,k$ ($1\leq n \leq 3\times 10^5$,$1\leq m \leq 6\times 10^5$,$2\leq k \leq 10000$),分别表示彩蛋个数、边数和网格图大小。

接下来 $n$ 行每行三个整数 $x_i,y_i,c_i$ ($1\leq x_i ,y_i \leq k$,$1\leq c_i \leq n$),表示第 $i$ 个彩蛋的坐标和种类,其中第 $1$ 个彩蛋的坐标一定为 $(1,1)$ ,第 $n$ 个彩蛋的坐标一定为 $(k,k)$。

接下来 $m$ 行每行两个整数 $u_i,v_i$ ($1\leq u_i, v_i \leq n$),表示第 $i$ 条有向边所连接的两个彩蛋的编号,设 $u_i$ 对应坐标为 $(x,y)$,数据保证 $v_i$ 对应坐标为 $(x+1,y)$ 或 $(x,y+1)$。

第$n+m+2$行一个整数$Q$ ($1\leq Q \leq 10^5$),表示游戏次数。

接下来 $Q$ 行每行一个整数 $q_i$ ($1\leq q_i \leq n$),表示第 $i$ 次游戏的初始所在彩蛋的编号。

输出格式

输出 $Q$ 行每行一个整数,表示第 $i$ 次游戏最多可以获取多少彩蛋。

样例

Input
14 16 5
1 1 1
2 1 2
2 2 1
3 2 3
2 3 4
2 4 3
3 4 1
4 2 1
4 3 4
4 4 3
5 3 5
5 4 1
4 5 4
5 5 5
1 2
2 3
3 4
3 5
4 8
5 6
6 7
7 10
8 9
9 10
9 11
10 12
10 13
11 12
12 14
13 14
5
1
2
7
10
14
Output
5
5
4
4
1

14 人解决,21 人已尝试。

16 份提交通过,共有 73 份提交。

5.8 EMB 奖励。

创建: 5 月,4 周前.

修改: 5 月,4 周前.

最后提交: 20 小时前.

来源: N/A

题目标签