Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C. Цикл
ограничение по времени на тест
2.5 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Турнир — ориентированный граф без петель, в котором каждая пара вершин соединена ровно одним ребром. То есть для любых двух вершин u и v (u ≠ v) либо есть ребро из u в v, либо есть ребро из v в u.

Дан турнир из n вершин. Требуется найти в нем цикл длины три.

Входные данные

В первой строке задано целое число n (1 ≤ n ≤ 5000). В следующих n строках задана матрица смежности графа A (без пробелов). Ai, j = 1, если в графе есть ребро из вершины i в вершину j, в противном случае Ai, j = 0. Ai, j обозначает j-ый символ в i-ой строке.

Гарантируется, что заданный граф является турниром, то есть Ai, i = 0, Ai, j ≠ Aj, i (1 ≤ i, j ≤ n, i ≠ j).

Выходные данные

Выведите три различные вершины графа a1, a2, a3 (1 ≤ ai ≤ n), такие что Aa1, a2 = Aa2, a3 = Aa3, a1 = 1, или «-1», если цикла длины три не существует.

Если решений несколько, выведите любое.

Примеры
Входные данные
5
00100
10000
01001
11101
11000
Выходные данные
1 3 2
Входные данные
5
01111
00000
01000
01100
01110
Выходные данные
-1