QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100

# 6167. 染色图的联通性问题

统计

染色图的联通性问题:给定一张 $N$ 个点 $M$ 条边的无向图,顶点标号为 $1,2,\cdots, N$,每个点有一个颜色 $c_i$。对于每个 $i = 1, 2, \cdots, N$,求出如果删去和顶点 $i$ 相邻的边,剩下的图里有多少对颜色相同的点处在不同联通快中。

输入格式

输入的第一行包含两个整数 $N, M$。

接下来一行包含 $N$ 个整数 $c_1, c_2, \cdots, c_N$。

接下来 $M$ 行,每行两个整数 $x, y$,描述一条边。

输出格式

输出 $n$ 行,每行一个整数。其中第 $i$ 行的整数表示删去点 $i$ 的答案。

样例数据

样例输入

9 16
2 7 3 2 1 1 1 3 4
1 2
4 2
2 7
1 7
3 6
1 3
1 4
1 5
5 2

样例输出

4
1
3
2
3
3
3
1
1

子任务

对于 $20\%$ 的数据,$N \leq 1\,000$。

对于 $100\%$ 的数据,$1 \leq N,M \leq 5 \times 10^5, 1 \leq c_i \leq N$。


  1. 赛时并未提供空间限制,“请选手自行评估” QOJ 上设置为 1 GB。