QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100
[0]

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

Statistics

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

输入格式

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

接下来一行包含 N 个整数 c1,c2,,cN

接下来 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% 的数据,N1000

对于 100% 的数据,1N,M5×105,1ciN


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