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

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

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

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

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

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

Вхідні дані

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

Вихідні дані

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

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

Приклади

Примітка

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

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

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

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