锦标赛是一种没有自环的有向图,其中每对顶点都由一条有向边连接。也就是说,对于任意两个顶点 u 和 v (u ≠ v) 都存在从 u 到 v 的边,或者从 v 到 u 的边。
给你一个由 n 个顶点组成的锦标赛。你的任务是找到一个长度为三的循环。
输入
第一行包含一个整数 n (1 ≤ n ≤ 5000)。接下来的 n 行包含图的邻接矩阵 A(不带空格)。如果图有从顶点 i 到顶点 j 的边,则 Ai, j = 1,否则 Ai, j = 0。Ai, j 代表第 i 行中的第 j 个字符。
保证给定的图是一个锦标赛,即 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”(如果不存在长度等于 3 的环)。
如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
5 00100 10000 01001 11101 11000
输出 #1
1 3 2
输入 #2
5 01111 00000 01000 01100 01110
输出 #2
-1