eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Цветной граф

Цветной граф

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

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

  • A = 1, если граф является красно-связным, A = 0, если нет

  • B = 1, если граф является сине-связным, B = 0, если нет

Например, состояние (1, 0) задает граф, который является красно-связным, но не сине-связным.

За один клик по ребру Лора может изменить его цвет (с синего на красный, либо с красного на синий). Цель игры заключается в том, чтобы по заданному начальному графу и желаемому состоянию добиться того, чтобы граф находился в этом состоянии, за минимальное количество кликов. Требуется написать программу, которая определяет, какое минимальное количество кликов потребуется Лоре, чтобы решить головоломку.

Вхідні дані

Первая строка содержит положительное целое число n (3n250) – количество вершин в графе. Далее следует 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
4
1 0 0 0
0 0 1 0
0 1 1 0
0 0 0 0
0 1
Вихідні дані #1
2
1 3
4 3
Вхідні дані #2
3
0 1 1
1 0 0
1 0 0
1 1
Вихідні дані #2
-1
Вхідні дані #3
3
0 1 1
1 0 0
1 0 0
0 1
Вихідні дані #3
0

Примітка

Красные ребра на рисунках изображены сплошными линиями, а синие - штрихованными. В первом пример исходно граф находится в состоянии (1, 0):

prb8561.gif

Изменив цвет ребер 1-3 и 4-3, мы преобразуем граф в состояние (0, 1), он выглядит таким образом:

prb8561_1.gif

Во втором примере легко понять, что граф с 3 вершинами и состоянием (1, 1) не существует.

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

Джерело 2017 IX International autumn tournament in informatics, Shumen, Senior, День 2, Задача E