染色图的联通性问题：给定一张 $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。