← 返回题目列表

Codeforces · 117/C

C. 循环

中文机器翻译题面 查看原题

锦标赛是一种没有自环的有向图,其中每对顶点都由一条有向边连接。也就是说,对于任意两个顶点 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