Codeforces Beta Round 88 |
---|
Закончено |
Турнир — ориентированный граф без петель, в котором каждая пара вершин соединена ровно одним ребром. То есть для любых двух вершин 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
Название |
---|