Кольорові компоненти

Обмеження: 2 сек., 512 МіБ

Вам задано неорієнтований простий граф \(G = (V, E)\), де \(|V| = n\) — кількість вершин, а \(|E| = m\) — кількість ребер. Кожна вершина \(v \in V\) має колір \(c_v\), заданий цілим числом.

Каркасним підграфом графа \(G\) називається граф \(G' = (V, E')\), де \(E' \subseteq E\), тобто він містить той самий набір вершин, але довільну підмножину ребер.

Зв’язна компонента графа називається кольоровою, якщо жодні дві вершини в ній не мають однакового кольору. Іншими словами, для кожного кольору \(\gamma\) у компоненті може бути не більше однієї вершини цього кольору.

Вершина називається ізольованою, якщо її степінь дорівнює \(0\), тобто вона утворює зв’язну компоненту, що складається лише з неї.

Ваше завдання — вибрати підмножину ребер \(E' \subseteq E\) та побудувати каркасний підграф \(G' = (V, E')\) так, щоб виконувалися такі умови:

• кожна зв’язна компонента графа \(G'\) є кольоровою;

• кількість ізольованих вершин у графі \(G'\) є якомога меншою.

Потрібно вивести мінімально можливу кількість ізольованих вершин та один відповідний каркасний підграф, який досягає цього мінімуму.

Вхідні дані

У першому рядку задано два цілі числа \(n\) і \(m\) — кількість вершин і ребер графа.

У другому рядку задано \(n\) цілих чисел \(c_1, c_2, \dots, c_n\), де \(c_i\) — колір вершини \(i\).

У кожному з наступних \(m\) рядків задано по два цілі числа \(u\) і \(v\), що описують неорієнтоване ребро між вершинами \(u\) та \(v\).

Вихідні дані

У першому рядку виведіть одне ціле число \(s\) — мінімально можливу кількість ізольованих вершин серед усіх каркасних підграфів \(G' = (V, E')\), у яких кожна зв’язна компонента є кольоровою.

У другому рядку виведіть ціле число \(k\) — кількість ребер у вибраній множині \(E'\).

У наступних \(k\) рядках виведіть по два цілі числа \(u\) та \(v\) — ребра множини \(E'\).

Буде зараховано будь-який каркасний підграф \(G' = (V, E')\), який задовольняє умови задачі та містить рівно \(s\) ізольованих вершин.

Обмеження

\(1 \le n \le 5 \cdot 10^3\),

\(1 \le m \le 5 \cdot 10^3\),

\(1 \le c_i \le n\),

гарантовано, що граф не містить кратних ребер і петель.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 4 1 1 2 2 1 3 1 4 2 3 2 4	0 2 1 3 2 4

Примітки

У прикладі одним з оптимальних розв’язків є вибір ребер \((1,3)\) та \((2,4)\). Тоді утворюються дві зв’язні компоненти: \(\{1,3\}\) та \(\{2,4\}\). Кожна компонента містить дві вершини різних кольорів, тому обидві є кольоровими. Кожна вершина має степінь щонайменше \(1\), отже ізольованих вершин немає, тобто відповідь дорівнює \(0\), і це є оптимальним.