{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"MD","content":"BaoBao is taking an online exam of the Kawa programming language, which consists of $n$ multiple choice questions. The exam is not easy, as for each question, BaoBao needs to select the one and only one correct answer from $10^5$ available choices! But don\u0027t worry, as an active committer of the famous *open-kdk*, BaoBao obviously knows all the correct answers.\n\nAlthough BaoBao is an expert in Kawa, the developers of the exam system are definitely not experts in software engineering. There are $m$ bugs in the exam system, and the $i$-th bug can be described as $(u_i, v_i)$, which means that BaoBao must select the same choice for question $u_i$ and $v_i$ (even if the choice he selects is incorrect!).\n\nTime is limited, and the exam must go on. The developers only have time to fix one bug. Now the developers are wondering, for all $1 \\le i \\le m$, what\u0027s the maximum possible number of questions BaoBao can correctly answer if they fix the $i$-th bug. Please write a program to solve this problem so that the developers can select a proper bug to fix.\n\n#### Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\n\nThe first line contains two integers $n$ and $m$ ($1 \\le n \\le 10^5$, $1 \\le m \\le 10^5$), indicating the number of questions and the number of bugs.\n\nThe second line contains $n$ integers $a_1, a_2, \\dots, a_n$ ($1 \\le a_i \\le 10^5$), where $a_i$ indicates the correct answer for question $i$.\n\nFor the following $m$ lines, the $i$-th line has two integers $u_i$ and $v_i$ ($1 \\le u_i, v_i \\le n$), indicating the $i$-th bug.\n\nIt\u0027s guaranteed that neither the sum of $n$ nor the sum of $m$ over all test cases will exceed $10^6$.\n\n#### Output\n\nFor each test case output one line containing $m$ integers $c_1, c_2, \\dots, c_m$ separated by a space, where $c_i$ indicates the maximum possible number of questions BaoBao can correctly answer if the $i$-th bug is fixed.\n\nPlease, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!\n\n### Sample:\n\n\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\n3\n7 5\n1 2 1 2 1 2 1\n1 2\n1 3\n2 4\n5 6\n5 7\n3 3\n1 2 3\n1 2\n1 3\n2 3\n2 3\n12345 54321\n1 2\n1 2\n1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\n6 5 5 5 4\n1 1 1\n1 1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n#### Hint\n\nThe following table explains the first sample test case.\n\n* The \"possible choices\" column indicates a possible set of choices to each question BaoBao can select, leading to a maximum possible number of correctly answered questions;\n* The \"correct\" column indicates the number of correctly answered questions using the set of choices provided in the \"possible choices\" column.\n\n\u003ccenter\u003e\n\u003ctable id\u003d\"problem-table\" style\u003d\"border-collapse: collapse; text-align: center;\" align\u003d\"center\"\u003e\n \u003cthead\u003e\n \u003ctr\u003e\u003cth\u003eBug No.\u003c/th\u003e\u003cth\u003ePossible Choices\u003c/th\u003e\u003cth\u003eCorrect\u003c/th\u003e\u003c/tr\u003e\n \u003c/thead\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\u003ctd\u003e1\u003c/td\u003e\u003ctd\u003e(1, 2, 1, 2, 1, 1, 1)\u003c/td\u003e\u003ctd\u003e6\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e2\u003c/td\u003e\u003ctd\u003e(2, 2, 1, 2, 1, 1, 1)\u003c/td\u003e\u003ctd\u003e5\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e3\u003c/td\u003e\u003ctd\u003e(1, 1, 1, 2, 1, 1, 1)\u003c/td\u003e\u003ctd\u003e5\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e4\u003c/td\u003e\u003ctd\u003e(1, 1, 1, 1, 1, 2, 1)\u003c/td\u003e\u003ctd\u003e5\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e5\u003c/td\u003e\u003ctd\u003e(1, 1, 1, 1, 1, 1, 1)\u003c/td\u003e\u003ctd\u003e4\u003c/td\u003e\u003c/tr\u003e\n \u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/center\u003e\n\nFor the second sample test case, no matter which bug is fixed, BaoBao has to select the same choice for all the three questions. As the correct answer for each question is different, BaoBao can only correctly answer 1 question.\n\nFor the third sample test case, note that even if the developers fix the first bug, the second bug is still taking effect and BaoBao still has to select the same choice for the two problems. It\u0027s the same if the second bug is fixed.\n\n\u003cstyle type\u003d\"text/css\"\u003e\n#problem-table \u003e thead \u003e tr \u003e th, #problem-table \u003e tbody \u003e tr \u003e td\n{\n padding: 3px 5px;\n border: 1px solid black;\n}\n\u003c/style\u003e\n"}}]}