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

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

2 секунди
512 мегабайтів
Дуже складна

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

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

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

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

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

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

Вхідні дані

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

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

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

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

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

1 \le c_i \le n,

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

Вихідні дані

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

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

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

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

Приклади

Приклад

Loading
Loading

Примітка

У прикладі одним з оптимальних розв’язків є вибір ребер та . Тоді утворюються дві зв’язні компоненти: та . Кожна компонента містить дві вершини різних кольорів, тому обидві є кольоровими. Кожна вершина має степінь щонайменше , отже ізольованих вершин немає, тобто відповідь дорівнює , і це є оптимальним.

Граф із прикладу.

Оптимальний кольоровий каркасний підграф G' для графа .