Fixing One Bug to Maximize Correct Answers

BaoBao is taking an online exam of the Kawa programming language consisting of \(n\) multiple choice questions, each having exactly one correct answer out of \(10^5\) choices. Although BaoBao knows all the correct answers, the exam system has \(m\) bugs. The \(i\)-th bug is given by a pair \((u_i, v_i)\) meaning that the answers for question \(u_i\) and \(v_i\) must be the same, even if that forces BaoBao to give an incorrect answer.

The developers have time to fix exactly one bug. For each bug \(i\) (\(1 \le i \le m\)), if that bug is fixed (i.e. the constraint \((u_i,v_i)\) is removed and all other constraints remain), what is the maximum possible number of questions BaoBao can answer correctly? In other words, when the remaining constraints force groups of questions to have the same answer, BaoBao may choose a common answer for each connected group so as to maximize the number of questions that match their correct answers. For a connected group (component) with questions having correct answers, his best score is the frequency of the most common correct answer in that group.

You are given \(n\), \(m\), an array of \(n\) integers representing the correct answers for each question, and \(m\) pairs \((u_i,v_i)\) representing the buggy constraints. For each bug fixed individually, compute and output the maximum number of questions BaoBao can answer correctly if that bug is fixed.

Note: Questions are numbered from 1 to \(n\). The answer for each bug fix should be computed independently from the original full set of constraints, with exactly the \(i\)-th bug removed.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1 \le n, m \le \text{reasonable limits})\), the number of questions and the number of bugs respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) \((1 \le a_i \le 10^5)\) representing the correct answers for each question.

The following \(m\) lines each contain two integers \(u_i\) and \(v_i\) \((1 \le u_i, v_i \le n)\); the \(i\)-th line describes that questions \(u_i\) and \(v_i\) must have the same answer due to the bug.

outputFormat

Output \(m\) lines. The \(i\)-th line should contain one integer — the maximum number of questions BaoBao can answer correctly if the \(i\)-th bug is fixed (i.e. the constraint \((u_i,v_i)\) is removed and all others remain).

sample

4 3
1 2 3 4
1 2
3 4
2 3

2
2
2