Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. Chef has recently set up a network between the N residents of the dormitory. Each resident owns a personal computer. There are direct connections between E pairs of computers. Pairs of computers not directly connected can still communicate if there is a path between them in the network.

All N residents are fans of Basketball, but each one has their own favorite team. The ith resident's favorite team is team Gi. Naturally, fans of the same team want to communicate with each other via the network.

Unfortunately, Chef isn't too knowledgeable about computers so he didn't ensure that all pairs of computers can communicate with each other. We call a pair of residents (i, j) sad if they have the same favorite team (i.e., Gi = Gj) but they can't communicate with each other. Thus, there can be many sad pairs in the network right now.

Even worse, from time to time, someone gets disconnected from the network, further increasing the number of sad pairs. When a resident is disconnected, all direct connections to and from his/her computer becomes unusable.

Chef didn't anticipate all these problems and has turned to you for help. Your first task is to submit a report containing N integers, where the ith integer is the number of sad pairs in the network if the ith resident was disconnected.

Input The first line contains two integers, N and E.

The second line contains N space-separated integers G1, G2, ..., GN denoting the residents' favorite teams.

The following E lines each contains two integers, ai and bi, which means that there is a direct connection between computers of resident ai and bi. Connections are bidirectional.

Output Output N lines. The ith line must contain a single integer, the number of sad pairs if the ith resident was disconnected from the network.

Constraints 5 ≤ N ≤ 2×105 1 ≤ Gi ≤ 106 0 ≤ E ≤ min(2×105, N(N-1)/2) 1 ≤ ai < bi ≤ N No pair (ai, bi) will appear more than once in the input. Subtasks Subtask #1: (25 points) Every computer can communicate with at most 59 other computers.

Subtask #2: (75 points) No additional constraints.

Example Input: 7 6 1 3 3 1 1 3 1 1 2 2 3 1 3 4 5 5 6 6 7

Output: 5 6 6 7 8 7 7 Explanation In the given network, residents 1, 4, 5 and 7 all have team 1 as their favorite, and 2, 3 and 6 all have team 3 as their favorite.

If resident 1 is disconnected, then there are 5 sad pairs: (1,4), (1,5), (1,7), (2,6), (3,6). If resident 2 is disconnected, then there are 6 sad pairs: (1,4), (1,5), (1,7), (2,3), (2,6), (3,6). If resident 3 is disconnected, then there are 6 sad pairs: (1,4), (1,5), (1,7), (2,3), (2,6), (3,6). If resident 4 is disconnected, then there are 7 sad pairs: (1,4), (1,5), (1,7), (2,6), (3,6), (4,5), (4,7). If resident 5 is disconnected, then there are 8 sad pairs: (1,4), (1,5), (1,7), (2,6), (3,6), (4,5), (4,7), (5,7). If resident 6 is disconnected, then there are 7 sad pairs: (1,4), (1,5), (1,7), (2,6), (3,6), (4,7), (5,7). If resident 7 is disconnected, then there are 7 sad pairs: (1,4), (1,5), (1,7), (2,6), (3,6), (4,7), (5,7).