#1615. 格斗俱乐部(beat)

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Violet956

题目描述

最近俱乐部举行了一场比赛,该比赛有N位选手参加,他们将围成一个圆圈,每一场比赛圈内任意的两位相邻的选手均可进行相互的格斗,胜利者将留在圈内进入下轮比赛而失败者则直接被送往医院(没有平局)。比赛是残酷的,最后圈内将只剩下一位选手,他将是总冠军。    我们做个奇怪的假设,两位选手进行格斗,他们比赛的结果总是确定的。虽然俱乐部的成员们都很喜欢格斗,但是他们仍然很希望能获得总冠军。现在你通过统计已经知道了任意两位选手格斗的结果,你有责任告诉每位选手,如果赛程合适安排的话,他是否可能成为总冠军。

输入格式

数据第一行是一个整数N,,表示比赛的选手数量。接下来给出一个N*N的“0”、“1”矩阵A(行内用空格隔开),第i行第j列为 1表示选手i能战胜选手j,否则选手j能战胜选手i。你可以假定Aij与Aji(i≠j)均是不同的且Aii=0。比赛开始时所有选手按顺时针方向由编号1到编号N站成一个圈,初始时编号1与编号N的选手是相邻的。

输出格式

输出包含N行,每行为一个整数“0”或“1”,“1”表示第i号选手有可能成为冠军,“0”表示不可能。

样例

输入样例#1

3
0 1 1
0 0 1
0 0 0

输出样例#1

1
0
0

数据范围与提示

30%1<=N<=8

60%1<=N<=50

100%1<=N<=200

Aij=0或1