题目描述

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

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

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

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

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

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

输入格式

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

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

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

输出格式

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

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

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

数据范围及约定

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