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 可以正确回答的最大问题数量是多少。

无

无

下表解释了第一个示例测试用例。 - “可能的选择”列表示 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 仍然必须为这两个问题选择相同的选项。如果第二个错误被修复，情况也是一样的。