4356: 「JOI 2016 Final」铁路票价

内存限制：256 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：0 解决：0

题目描述

**本题译自 [JOI 2016 Final](https://www.ioi-jp.org/joi/2015/2016-ho/index.html) T3「[鉄道運賃](https://www.ioi-jp.org/joi/2015/2016-ho/2016-ho.pdf)」** 给出一个包含 $N$ 个点，$M$ 条无向边的图，点的编号为 $1\ldots N$，边的编号为 $1\ldots M$。 $i$ 号边 $(1\leqslant i\leqslant M)$ 连接结点 $U_i$ 和 $V_i$。开始时，每条边的长度为 $1$ 。 接下来有 $Q$ 次修改，第 $j$ 次修改 $(1\leqslant j\leqslant Q)$ 会将 $R_j$ 号边的长度由 $1$ 修改为 $2$ 。保证每条边最多只修改一次。 每次修改后，试求：与原图（未作任何修改的图）相比，有多少结点到结点 $1$ 的最短路变长了。

输入

第一行有三个整数 $N, M, Q$，用空格分隔。 在接下来的 $M$ 行中，第 $i(1\leqslant i\leqslant M)$ 行有两个整数 $U_i, V_i$，用空格分隔。 在接下来的 $Q$ 行中，第 $j(1\leqslant j\leqslant Q)$ 行有一个整数 $R_j$。 输入的所有数的含义见题目描述。

输出

输出共 $Q$ 行，第 $j(1\leqslant j\leqslant Q)$ 行有一个整数，表示第 $j$ 次修改后，与原图相比，有多少结点到结点 $1$ 的最短路变长了。

样例输入 复制 

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 


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

输出样例2 


1
1
2
2
3
3

输入样例3 


2 1 1
1 2
1

输出样例3 


1

数据范围：对于 $12\%$ 的数据，$N\leqslant 100, M\leqslant 4950, Q\leqslant 30$。 对于另外 $14\%$ 的数据，$Q\leqslant 30$。 对于另外 $35\%$ 的数据，将输出的 $Q$ 个整数去重后不超过 $50$ 个。 对于所有数据，$2\leqslant N\leqslant 10^5, 1\leqslant Q\leqslant M\leqslant 2\times 10^5; 1\leqslant U_i, V_i\leqslant N, U_i ≠ V_i(1\leqslant i\leqslant M); 1\leqslant R_j\leqslant M, R_j ≠ R_k(1\leqslant j

来源/分类

提交提交记录统计讨论版露一手!