[ICPC2018 Qingdao R] Kawa Exam

BaoBao 正在参加 Kawa 编程语言的在线考试，该考试由 $n$ 个多项选择题组成。考试并不容易，对于每一道题，BaoBao 都需要从 $10^5$ 个可用选项中选择唯一一个正确答案！但别担心，作为著名的 $\text{open-kdk}$ 的积极参与者，BaoBao 显然知道所有正确的答案。 虽然 BaoBao 是 Kawa 方面的专家，但考试系统的开发人员绝对不是软件工程方面的专家。考试系统中有 $m$ 个错误，第 $i$ 个错误可以描述为 $(u_i,v_i)$，这意味着 BaoBao 必须为第 $u_i$ 和 $v_i$ 个问题选择相同的选项（即使他选择的选项不正确！）。 但是考试必须继续，这就意味着开发人员只有时间修复一个错误。现在，开发人员想知道，对于所有的 $1\le i\le m$，如果他们修复 $i$，BaoBao 可以正确回答的最大问题数量是多少。 ## 输入格式 有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例： 第一行包含两个整数 $n$ 和 $m$（$1\le n\le 10^5$，$1\le m\le 10^5$），表示问题数量和错误数量。 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 10^5$），其中 $a_i$ 表示问题 $i$ 的正确答案。 对于以下 $m$ 行，第 $i$ 行有两个整数 $u_i$ 和 $v_i$（$1\le u_i,v_i\le n$），表示第 $i$ 个错误。 保证所有测试用例的 $n$ 和 $m$ 的总和都不会超过 $10^6$。 ## 输出格式 对于每个测试用例的输出，一行包含由空格分隔的 $m$ 个整数 $c_1,c_2,\dots,c_m$，其中 $c_i$ 表示如果修复了第 $i$ 个错误，BaoBao 可以正确回答的最大问题数。 请不要在每行末尾输出多余的空格，否则您的答案可能会被认为是错误的！ ## 提示 下表解释了第一个示例测试用例。 - “可能的选择”列表示 BaoBao 可以选择的每个问题的一组可能的选择，从而导致正确回答的问题的最大可能数量； - “正确”列表示使用“可能的选择”列中提供的一组选择正确回答的问题的数量。 $$\begin{array}{|c|c|c|c|} \hline \textbf{Bug 编号} & \textbf{可能的选择} & \textbf{正确} \\ \hline 1 & (1, 2, 1, 2, 1, 1, 1) & 6 \\ \hline 2 & (2, 2, 1, 2, 1, 1, 1) & 5 \\ \hline 3 & (1, 1, 1, 2, 1, 1, 1) & 5 \\ \hline 4 & (1, 1, 1, 1, 1, 2, 1) & 5 \\ \hline 5 & (1, 1, 1, 1, 1, 1, 1) & 4 \\ \hline \end{array}$$ 对于第二个样本测试用例，无论哪个 bug 被修复，BaoBao 都必须为所有三个问题选择相同的选项。由于每个问题的正确答案不同，BaoBao 只能正确回答一个问题。 对于第三个示例测试用例，请注意，即使开发人员修复了第一个错误，第二个错误仍然有效，BaoBao 仍然必须为这两个问题选择相同的选项。如果第二个错误被修复，情况也是一样的。

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't worry, as an active committer of the famous \textit{open-kdk}, BaoBao obviously knows all the correct answers. Although 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!). Time 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's 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.

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The 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. The 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$. For 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. It's guaranteed that neither the sum of $n$ nor the sum of $m$ over all test cases will exceed $10^6$.

For 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. Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!

3
7 5
1 2 1 2 1 2 1
1 2
1 3
2 4
5 6
5 7
3 3
1 2 3
1 2
1 3
2 3
2 3
12345 54321
1 2
1 2
1 1

6 5 5 5 4
1 1 1
1 1 1

The following table explains the first sample test case. - 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; - The ``correct`` column indicates the number of correctly answered questions using the set of choices provided in the ``possible choices`` column. $$\begin{array}{|c|c|c|c|} \hline \textbf{Bug No.} & \textbf{Possible Choices} & \textbf{Correct} \\ \hline 1 & (1, 2, 1, 2, 1, 1, 1) & 6 \\ \hline 2 & (2, 2, 1, 2, 1, 1, 1) & 5 \\ \hline 3 & (1, 1, 1, 2, 1, 1, 1) & 5 \\ \hline 4 & (1, 1, 1, 1, 1, 2, 1) & 5 \\ \hline 5 & (1, 1, 1, 1, 1, 1, 1) & 4 \\ \hline \end{array}$$ For 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. For 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's the same if the second bug is fixed.