题目描述

有一个$n$个点$m$条边的无向图，点和边都从$0$开始编号。共$Q$次询问，每次询问一个编号$x$，要求回答删去编号为$x$的边后，会有多少个无序点对($u, v$)将不能相互到达?

输入

第一行三个整数$n,m,Q$分别代表点数边数询问数。 接下来$m$行每行两个整数$u,v$表示$u$与$v$之间有一条边。注意可能有重边和自环。 接下来$Q$行每行一个整数$x$表示询问的边的编号。

输出

输出Q行每行一个整数，表示询问的答案，结果保留后三位(即模$1000$)。

输入样例

4 3 3
0 1
1 0
0 2
0
1
2

输出样例

3
3
5

提示

【数据规模】 30％的数据：$n，m，Q≤100$； 60％的数据：$n，m，Q≤1000$； 100％的数据：$1≤n≤10^5，1≤m≤10^6，1≤Q≤8×10^5，0≤u，v＜n，0≤x＜m$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。