Chef and Sad Pairs

All submissions for this problem are available.
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 G_{i}. 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., G_{i} = G_{j}) 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 spaceseparated integers G_{1}, G_{2}, ..., G_{N} denoting the residents' favorite teams.
The following E lines each contains two integers, a_{i} and b_{i}, which means that there is a direct connection between computers of resident a_{i} and b_{i}. 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×10^{5}
 1 ≤ G_{i} ≤ 10^{6}
 0 ≤ E ≤ min(2×10^{5}, N(N1)/2)
 1 ≤ a_{i} < b_{i} ≤ N
 No pair (a_{i}, b_{i}) 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).
Author:  kevinsogo 
Editorial  http://discuss.codechef.com/problems/SADPAIRS 
Tags  hard, june16, kevinsogo, treedp 
Date Added:  30052016 
Time Limit:  1.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions