染色图的联通性问题:给定一张 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% 的数据,N≤1000。
对于 100% 的数据,1≤N,M≤5×105,1≤ci≤N。
注
- 赛时并未提供空间限制,
“请选手自行评估”QOJ 上设置为 1 GB。