Problem11358--洛谷P1710 - 地铁涨价

11358: 洛谷P1710 - 地铁涨价

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

Description

博艾市除了有海底高铁连接中国大陆、台湾与日本,市区里也有很成熟的轨道交通系统。我们可以认为博艾地铁系统是一个无向连通图。博艾有 $N$ 个地铁站,同时有 $M$ 小段地铁连接两个不同的站。

地铁计价方式很简单。从 A 站到 B 站,每经过一小段铁路(连接直接相邻的两个点的一条边),就要收取 $1$ 博艾元。也就是说,从 A 站到 B 站,选择的路径不一样,要价也会不同。

我们认为凡华中学在 $1$ 号地铁站。学生们通过地铁通勤,他们当然知道选择最短路来坐车的话,票价最便宜。

然而博艾地铁公司经营不善,一直亏损,于是他们打算提价。提价一次就是将一小段铁路原来收费 $1$ 元改收 $2$ 元。同一小段的铁路不会多次提价。他们打算提价 $Q$ 次。

学生们知道,如果他们到学校的一条最短路径中的一小段提价了,可以改变路径,使总票价不变。然而随着一条一条的铁路被提价,当居住在某个站附近的学生发现,提价后,没有任何一种方案可以从家到学校的费用和初始费用相等时,就会不满。

现在地铁公司希望知道,对于每一次涨价,有多少个站,学生会因为涨价而不满呢?

Input

第一行为三个整数 $N,M,Q$。

接下来 $M$ 行,每行 $2$ 个整数 $a_i,b_i,$ 表示第 $i$ 条铁路连接的两个站。$i$ 表示铁路编号。

接下来 $Q$ 行,每行一行整数 $r_j$,表示每次涨价的铁路编号。

Output

输出共 $Q$ 行。每行一个整数表示不满的车站数量。

Constraints

- 对于 $20\%$ 的数据 $N \le 100,Q \le 30$。
- 对于 $40\%$ 的数据 $Q \le 30$。
- 对于 $70\%$ 的数据正确的输出结果中,不会有超过 $50$ 种不一样的整数(数据范围剧透解法系列)
- 对于 $100\%$ 的数据 $N \le 100000,Q \le M \le 200000$。

Sample 1 Input

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

Sample 1 Output

0
2
2
4
4
次数 车站2 车站3 车站4 车站5
初始 1     1     2     2
1    1     1     2     2
2    1     2     2     3
3    1     2     2     3
4    2     2     3     3
5    2     2     4     3

HINT

洛谷P1710.

Source/Category