Цветной граф

Лора играет в онлайн-головоломку. У нее есть неориентированный граф с 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) не существует.

В третьем примере граф исходно уже находится в требуемом состоянии.