Given an undirected graph with $N$ vertices and $M$ edges, where vertices are labeled $1, 2, \dots, N$ and each vertex $i$ has a color $c_i$. For each $i = 1, 2, \dots, N$, calculate how many pairs of vertices with the same color are in different connected components if all edges incident to vertex $i$ are removed.

Input

The first line contains two integers $N$ and $M$.

The next line contains $N$ integers $c_1, c_2, \dots, c_N$.

The next $M$ lines each contain two integers $x, y$, describing an edge.

Output

Output $N$ lines, each containing one integer. The integer on the $i$-th line represents the answer after removing vertex $i$.

Examples

Input 1

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

Output 1

4
1
3
2
3
3
3
1
1

Subtasks

For $20\%$ of the data, $N \leq 1\,000$.

For $100\%$ of the data, $1 \leq N, M \leq 5 \times 10^5, 1 \leq c_i \leq N$.