P9886 [ICPC 2018 Qingdao R] Kawa Exam

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.

N/A

N/A

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.