• 色が同じである部員のペアが存在する場合、どちらかの部員に呪文を唱え、全ての部員の色と違う色に変えることで、\(N\) 人の色の種類数を \(1\) 増やすことができる。
• 呪文を唱えたことで \(N\) 人の色の種類数が減ることはない。
• \(N\) 人の色の種類数の上限は \(N\) である。

上の性質に着目すると、呪文を唱えるまえの \(N\) 人の色の種類数を \(K\) として、\(\min(K+M,\ N)\) が答えです。

\(K\) を求める方法を考えます。

配列 \(B\) を用意し、はじめ \(B_0 = B_1 = \dots = B_{200000} = 0\) とします。\(A_1\) から \(A_N\) のそれぞれの値 \(a\) に対して \(B_a = 1\) とすると、\(B\) の要素の和が \(K\) です。

以上より、\(\Theta(N)\) 時間でこの問題を解くことができました。実装例 (C++ 53 ms)

重複を省いた集合を表すデータ構造（C++ であれば std::set）を用いることでより簡単に \(K\) を求めることができます。時間計算量 \(\Theta (N \log N)\) です。実装例 (C++ 110 ms)

実際に「呪文を唱える」ことで答えを直接求めることが可能です。実装例 (C++ 97 ms)