地铁涨价

题目背景

本题开O2优化,请注意常数

题目描述

博艾市除了有海底高铁连接中国大陆、台湾与日本,市区里也有很成熟的轨道交通系统。我们可以认为博艾地铁系统是一个无向连通图。博艾有N个地铁站,同时有M小段地铁连接两个不同的站。 地铁计价方式很简单。从A站到B站,每经过一小段铁路(连接直接相邻的两个点的一条边),就要收取1博艾元。也就是说,从A站到B站,选择的路径不一样,要价也会不同。 我们认为凡华中学在1号地铁站。学生们通过地铁通勤,他们当然知道选择最短路来坐车的话,票价最便宜。 然而博艾地铁公司经营不善,一直亏损,于是他们打算提价。提价一次就是将一小段铁路原来收费1元改收2元。同一小段的铁路不会多次提价。他们打算提价Q次。 学生们知道,如果他们到学校的一条最短路径中的一小段提价了,可以改变路径,使总票价不变。然而随着一条一条的铁路被提价,当居住在某个站附近的学生发现,提价后,没有任何一种方案可以从家到学校的费用和初始费用相等时,就会不满。 现在地铁公司希望知道,对于每一次涨价,有多少个站,学生会因为涨价而不满呢?

输入输出格式

输入格式


第一行为三个整数N,M,Q。 接下来M行,每行2个整数ai,bi,表示第i条铁路连接的两个站。i表示铁路编号。 接下来Q行,每行一行整数rj,表示每次涨价的铁路编号。

输出格式


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

输入输出样例

输入样例 #1

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

输出样例 #1

0
2
2
4
4

说明

【样例解释】 ```cpp 次数 车站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 ``` 【数据范围】 对于20%的数据 N≤100, Q≤30 对于40%的数据 Q≤30 对于70%的数据 正确的输出结果中,不会有超过50种不一样的整数(数据范围剧透解法系列) 对于100%的数据 N≤100000, Q≤M≤200000