← 返回题目

题库练习 Cycle

← 上一题下一题 →

A8169 | $Cycle$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

A tournament is a directed graph without self-loops in which every pair of vertexes is connected by exactly one directed edge. That is, for any two vertexes $u$ and $v$ ( $u\neqv$ ) exists either an edge going from $u$ to $v$ , or an edge from $v$ to $u$ . You are given a tournament consisting of $n$ vertexes. Your task is to find there a cycle of length three.

输入格式

The first line contains an integer $n$ ( $1<=n<=5000$ ). Next $n$ lines contain the adjacency matrix $A$ of the graph (without spaces). $A_{i,j}=1$ if the graph has an edge going from vertex $i$ to vertex $j$ , otherwise $A_{i,j}=0$ . $A_{i,j}$ stands for the $j$ -th character in the $i$ -th line. It is guaranteed that the given graph is a tournament, that is, $A_{i,i}=0,A_{i,j}≠A_{j,i}$ $(1<=i,j<=n,i≠j)$ .

输出格式

Print three distinct vertexes of the graph $a_{1}$ , $a_{2}$ , $a_{3}$ ( $1<=a_{i}<=n$ ), such that $A_{a1},a_{2}=A_{a2},a_{3}=A_{a3},a_{1}=1$ , or "-1", if a cycle whose length equals three does not exist. If there are several solutions, print any of them.

输入输出样例

输入 #1

输出 #1

1 3 2

输入 #2

输出 #2

-1

C++ 编辑器

输入

输出