染色图的联通性问题：给定一张 $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$。
注
- 赛时并未提供空间限制，
“请选手自行评估”QOJ 上设置为 1 GB。