Вам задано неорієнтований простий граф G = (V, E), де |V| = n — кількість вершин, а |E| = m — кількість ребер. Кожна вершина v \in V має колір c_v, заданий цілим числом.
Каркасним підграфом графа називається граф G' = (V, E'), де E' \subseteq E, тобто він містить той самий набір вершин, але довільну підмножину ребер.
Зв’язна компонента графа називається кольоровою, якщо жодні дві вершини в ній не мають однакового кольору. Іншими словами, для кожного кольору у компоненті може бути не більше однієї вершини цього кольору.
Вершина називається ізольованою, якщо її степінь дорівнює , тобто вона утворює зв’язну компоненту, що складається лише з неї.
Ваше завдання — вибрати підмножину ребер E' \subseteq E та побудувати каркасний підграф G' = (V, E') так, щоб виконувалися такі умови:
кожна зв’язна компонента графа G' є кольоровою;
кількість ізольованих вершин у графі G' є якомога меншою.
Потрібно вивести мінімально можливу кількість ізольованих вершин та один відповідний каркасний підграф, який досягає цього мінімуму.
У першому рядку задано два цілі числа і — кількість вершин і ребер графа.
У другому рядку задано цілих чисел 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'), який задовольняє умови задачі та містить рівно ізольованих вершин.
Приклад
У прикладі одним з оптимальних розв’язків є вибір ребер та . Тоді утворюються дві зв’язні компоненти: та . Кожна компонента містить дві вершини різних кольорів, тому обидві є кольоровими. Кожна вершина має степінь щонайменше , отже ізольованих вершин немає, тобто відповідь дорівнює , і це є оптимальним.
Граф із прикладу.
Оптимальний кольоровий каркасний підграф G' для графа .