P9886 [ICPC 2018 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 仍然必须为这两个问题选择相同的选项。如果第二个错误被修复，情况也是一样的。