eolymp
bolt
Try our new interface for solving problems
Məsələlər

Полный граф - 2

Полный граф - 2

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Обсуждая личную жизнь всевозможных злодеев, мы обделили своим вниманием графа Дуку. Так вот, граф Дуку на досуге любит складывать оригами. Он давно систематизировал свои познания в этой области следующим образом: всего граф знает n фигурок, причем для некоторых из них он знает, как получать из одной другую. Для обучения начинающих ситхов Дуку разработал специальную таблицу. В ячейке [i, j] таблицы стоит "1", если граф может получить из фигурки i фигурку j одним сгибом. Иначе там стоит "0". Изначально в руках у графа Дуку чистый лист, то есть фигурка номер x по его системе, сложить же он желает журавлика – фигурку номер y.

Найдите, за сколько операций граф достигнет желаемого.

Giriş verilənləri

В первой строке находится число n (1n1000). В следующих n строках задана таблица Дуку. В (n + 1) - ой строке стоят числа x и y.

Çıxış verilənləri

Выведите минимальное количество операций, которые придется осуществить. Если же коварным планам Графа не суждено осуществиться, выведите "-1".

prb5338.gif

Nümunə

Giriş verilənləri #1
4
0 0 1 0
0 0 0 1
1 0 0 1
0 1 1 0
1 2
Çıxış verilənləri #1
3