Cycle

题意翻译

一个 $\texttt{tournament}$ 是一个没有自环的有向图，同时，每两个点之间有一条边连接。这就是说，对于两个点 $u,v (u\neq v)$，有一条从 $u$ 到 $v$ 的边或一条从 $v$ 到 $u$ 的边。 给你一个 $\texttt{tournament}$，请找出一个长度为 $3$ 的环。 **【输入格式】** 第一行一个正整数 $n$。 接下来 $n$ 行：一个 $n \times n$ 的邻接矩阵 $a$，由 `0` 和 `1` 组成。 若 $a_{i,j}=1$，表示有一条路从 $i$ 通往 $j$。 数据保证 $a_{i,i}=0$ 并且 $a_{i,j} \neq a_{j,i}$。 **【输出格式】** 仅一行：任意一种解决方案；若没有，输出 `-1`。

题目描述

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≠v $ ) 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

5
00100
10000
01001
11101
11000

输出样例 #1

1 3 2 

输入样例 #2

5
01111
00000
01000
01100
01110

输出样例 #2

-1

题意翻译

一个 $\texttt{tournament}$ 是一个没有自环的有向图，同时，每两个点之间有一条边连接。这就是说，对于两个点 $u,v (u\neq v)$，有一条从 $u$ 到 $v$ 的边或一条从 $v$ 到 $u$ 的边。 给你一个 $\texttt{tournament}$，请找出一个长度为 $3$ 的环。 **【输入格式】** 第一行一个正整数 $n$。 接下来 $n$ 行：一个 $n \times n$ 的邻接矩阵 $a$，由 `0` 和 `1` 组成。 若 $a_{i,j}=1$，表示有一条路从 $i$ 通往 $j$。 数据保证 $a_{i,i}=0$ 并且 $a_{i,j} \neq a_{j,i}$。 **【输出格式】** 仅一行：任意一种解决方案；若没有，输出 `-1`。