题目描述

给定一个竞赛图（即没有自环的有向完全图），也就是说图中的每对顶点都恰好由一条有向边连接，对于任何两个顶点 \(u\) 和 \(v\)（\(u≠v\)）都存在从 \(u\) 到 \(v\) 的边，或者从 \(v\) 到 \(u\) 的边。

请找出图中的某个三元环（长度为 \(3\) 的环），或者判断不存在这样的环。

格式

输入格式

第一行包含一个整数 \(n\)，表示图中顶点个数。

接下来 \(n\) 行描述这个图的邻接矩阵（没有空格），其中 \(A[i, j] = 1\) 表示存在一条 \(i\) 到 \(j\) 的边，否则 \(A[i, j]  = 0\)。

保证\(A[i, i] = 0,  A[i, j] ≠ A[j, i] (1≤ i, j ≤n, i ≠ j)\)。

输出格式

如果无解，输出 \(-1\)；否则输出三个不同的顶点\(x, y, z\) 使得\(A[x, y] = 1, A[y, z] = 1, A[z, x] = 1\)。输出 \(x,y\) 和 \(z\) 都最小的解即可。

样例1

样例输入1

5
00100
10000
01001
11101
11000

样例输出1

1 3 2

限制

\(20\%\)的数据：\(n ≤10\)；

\(50\%\)的数据：\(n ≤100\)；

\(100\%\)的数据：\(1≤ n ≤2000，A[i, j]∈\{0,1\}\)。