Кольоровий граф#8561

Кольоровий граф

1 секунда

128 мегабайтів

Складна

Лора грає в онлайн-головоломку. У неї є неорієнтований граф з $n$ вершинами, пронумерованими від $1$ до $n$ . Граф влаштований так, що будь-які дві різні вершини з'єднані ребром, яке пофарбоване або в синій, або в червоний колір. Граф називається червоно-зв'язним, якщо від будь-якої вершини можна дістатися до будь-якої іншої, використовуючи тільки червоні ребра. Аналогічно, граф синьо-зв'язний, якщо від будь-якої вершини можна дістатися до будь-якої іншої, використовуючи тільки сині ребра. Стан графа визначається парою чисел $(A, B)$ , де:

$A = 1$ A = 1, якщо граф є червоно-зв'язним, $A = 0$ A = 0, якщо ні
$B = 1$ B = 1, якщо граф є синьо-зв'язним, $B = 0$ B = 0, якщо ні

Наприклад, стан $(1, 0)$ означає, що граф є червоно-зв'язним, але не синьо-зв'язним.

За один клік по ребру Лора може змінити його колір (з синього на червоний або з червоного на синій). Мета гри полягає в тому, щоб, маючи початковий граф і бажаний стан, досягти цього стану за мінімальну кількість кліків. Необхідно написати програму, яка визначить, яка мінімальна кількість кліків потрібна Лорі, щоб вирішити головоломку.

Вхідні дані

Перший рядок містить додатне ціле число $n$ ( $3 \leq n \leq 250$ 3 \le n \le 250) – кількість вершин у графі. Далі йдуть $n$ рядків по $n$ цілих чисел, які задають кольори ребер. Позначимо $j$ -е число $i$ -го рядка як $G_{ij}$ G_{ij}. Якщо $G_{ij} = 0$ G_{ij} = 0, то ребро між вершинами $i$ і $j$ червоне, якщо $G_{ij} = 1$ G_{ij} = 1, то ребро між вершинами $i$ і $j$ синє. Гарантується, що $G_{ij} = G_{j i}$ G_{ij} = G_{ji}. Для $i = j$ i = j значення $G_{ij}$ G_{ij} не має значення, оскільки в графі немає петель. Останній рядок містить два цілі числа, розділені пробілом - $A$ і $B$ , що задають потрібний стан графа.

Вихідні дані

Якщо перетворити граф у потрібний стан неможливо, виведіть $- 1$ на єдиному рядку виводу.

Інакше перший рядок повинен містити ціле число $k$ - мінімальну кількість кліків, яку Лора повинна зробити, щоб перетворити граф у потрібний стан. Кожен з наступних $k$ рядків повинен містити два цілі числа - кінці ребра, яке слід перефарбувати черговим кліком. Якщо є декілька оптимальних рішень, можна вивести будь-яке з них. Ребра можна виводити в будь-якому порядку, аналогічно кінці ребер можна виводити в будь-якому порядку.

Приклади

Приклад 1

Приклад 2

Приклад 3

Примітка

Червоні ребра на рисунках зображені суцільними лініями, а сині - штрихованими. У першому прикладі початково граф знаходиться в стані $(1, 0)$ :

Змінивши колір ребер $1$ - $3$ і $4$ - $3$ , ми перетворюємо граф у стан $(0, 1)$ , і він виглядає так:

У другому прикладі легко зрозуміти, що граф з $3$ вершинами і станом $(1, 1)$ не існує.

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