{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/JUNE16/mandarin/SADPAIRS.pdf\"\u003eMandarin Chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/JUNE16/russian/SADPAIRS.pdf\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/JUNE16/vietnamese/SADPAIRS.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\r\n\r\n\u003cp\u003eChef has recently set up a network between the \u003cb\u003eN\u003c/b\u003e residents of the dormitory. Each resident owns a personal computer. There are direct connections between \u003cb\u003eE\u003c/b\u003e pairs of computers. Pairs of computers not directly connected can still communicate if there is a path between them in the network.\u003c/p\u003e\r\n\r\n\u003cp\u003eAll \u003cb\u003eN\u003c/b\u003e residents are fans of Basketball, but each one has their own favorite team. The \u003cb\u003ei\u003c/b\u003eth resident\u0027s favorite team is team \u003cb\u003eG\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e. Naturally, fans of the same team want to communicate with each other via the network.\u003c/p\u003e\r\n\r\n\u003cp\u003eUnfortunately, Chef isn\u0027t too knowledgeable about computers so he didn\u0027t ensure that all pairs of computers can communicate with each other. We call a pair of residents \u003cb\u003e(i, j)\u003c/b\u003e \u003cb\u003esad\u003c/b\u003e if they have the same favorite team (i.e., \u003cb\u003eG\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d \u003cb\u003eG\u003csub\u003ej\u003c/sub\u003e\u003c/b\u003e) but they can\u0027t communicate with each other. Thus, there can be many sad pairs in the network right now.\u003c/p\u003e\r\n\r\n\u003cp\u003eEven 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.\u003c/p\u003e\r\n\r\n\u003cp\u003eChef didn\u0027t anticipate all these problems and has turned to you for help. Your first task is to submit a report containing \u003cb\u003eN\u003c/b\u003e integers, where the \u003cb\u003ei\u003c/b\u003eth integer is \u003ci\u003ethe number of sad pairs in the network if the \u003cb\u003ei\u003c/b\u003eth resident was disconnected\u003c/i\u003e.\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eThe first line contains two integers, \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eE\u003c/b\u003e.\u003c/p\u003e\r\n\u003cp\u003eThe second line contains \u003cb\u003eN\u003c/b\u003e space-separated integers \u003cb\u003eG\u003csub\u003e1\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eG\u003csub\u003e2\u003c/sub\u003e\u003c/b\u003e, ..., \u003cb\u003eG\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e denoting the residents\u0027 favorite teams.\u003c/p\u003e\r\n\u003cp\u003eThe following \u003cb\u003eE\u003c/b\u003e lines each contains two integers, \u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, which means that there is a direct connection between computers of resident \u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e. Connections are bidirectional.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eOutput \u003cb\u003eN\u003c/b\u003e lines. The \u003cb\u003ei\u003c/b\u003eth line must contain a single integer, the number of sad pairs if the \u003cb\u003ei\u003c/b\u003eth resident was disconnected from the network.\u003c/p\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cb\u003e5\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e2×10\u003csup\u003e5\u003c/sup\u003e\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eG\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e6\u003c/sup\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e0\u003c/b\u003e ≤ \u003cb\u003eE\u003c/b\u003e ≤ \u003cb\u003emin(2×10\u003csup\u003e5\u003c/sup\u003e, \u003cb\u003eN(N-1)/2\u003c/b\u003e)\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003c \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003eNo pair (\u003cb\u003ea\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e) will appear more than once in the input.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eSubtasks\u003c/h3\u003e\r\n\u003cp\u003e\r\n\u003cb\u003eSubtask #1: (25 points)\u003c/b\u003e Every computer can communicate with at most 59 other computers.\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\n\u003cb\u003eSubtask #2: (75 points)\u003c/b\u003e No additional constraints.\r\n\u003c/p\u003e\r\n\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\r\n\u003ctt\u003e7 6\r\n1 3 3 1 1 3 1\r\n1 2\r\n2 3\r\n1 3\r\n4 5\r\n5 6\r\n6 7\r\n\u003c/tt\u003e\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n\u003ctt\u003e5\r\n6\r\n6\r\n7\r\n8\r\n7\r\n7\r\n\u003c/tt\u003e\u003c/pre\u003e\r\n\r\n\u003ch3\u003eExplanation\u003c/h3\u003e\r\n\u003cp\u003eIn 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.\u003c/p\u003e\r\n\u003cul\u003e\r\n\u003cli\u003eIf resident 1 is disconnected, then there are 5 sad pairs: (1,4), (1,5), (1,7), (2,6), (3,6).\u003c/li\u003e\r\n\u003cli\u003eIf resident 2 is disconnected, then there are 6 sad pairs: (1,4), (1,5), (1,7), (2,3), (2,6), (3,6).\u003c/li\u003e\r\n\u003cli\u003eIf resident 3 is disconnected, then there are 6 sad pairs: (1,4), (1,5), (1,7), (2,3), (2,6), (3,6).\u003c/li\u003e\r\n\u003cli\u003eIf resident 4 is disconnected, then there are 7 sad pairs: (1,4), (1,5), (1,7), (2,6), (3,6), (4,5), (4,7).\u003c/li\u003e\r\n\u003cli\u003eIf 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).\u003c/li\u003e\r\n\u003cli\u003eIf resident 6 is disconnected, then there are 7 sad pairs: (1,4), (1,5), (1,7), (2,6), (3,6), (4,7), (5,7).\u003c/li\u003e\r\n\u003cli\u003eIf resident 7 is disconnected, then there are 7 sad pairs: (1,4), (1,5), (1,7), (2,6), (3,6), (4,7), (5,7).\u003c/li\u003e\r\n\u003c/ul\u003e\r\n"}}]}