UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2615. 超级斗兽棋

Statistics 下载数据

Description

    斗兽棋是一项有趣的棋类游戏。双方分别控制一些动物,在棋盘上按照一定的规则轮流行动,先占领对方巢穴为胜。任意两种不同的动物AB相遇,要么AB,要么BA
    不过,原先的斗兽棋中动物种类较少,玩久了就会略显无聊。于是,某公司决定开发一种超级斗兽棋,含有N种动物,编号为1,2,……,N,并已经制定好了任意两种不同动物相遇时的胜负关系。
    下一步工作是测试超级斗兽棋的趣味性。经调查发现,若动物间相互制约,则游戏的趣味性将大大增加。所谓动物间相互制约,即可以将动物按某种次序排成一个序列P1P2,……,Pn,满足P1P2P2P3,……,Pn-1)胜PnPnP1。如果动物间不能相互制约,但可以半相互制约(在相互制约的条件中去掉“PnP1,其他条件不变)的话,那么这款游戏虽然趣味性有所降低,但勉强可以接受。不过,如果连半相互制约都不能满足的话,呵呵,对不起,重新设计吧。
    你的任务就是帮助测试这款超级斗兽棋的趣味性。
 

Input

第一行是一个整数n,表示动物种类数。接下来是一个n*n的矩阵,为动物间的胜负关系,第i行第j列为1ij,为0ji(保证胜负关系不会矛盾,即不同的ij相遇有且仅有一个胜者;主对角线上全为0)。
 
第一行是一个整数s,表示测试结果:0表示动物间相互制约,1表示动物间不相互制约但半相互制约,-1表示都不满足。若测试结果不为-1,则在第二行输出满足响应条件的任一序列P(即测试结果为0时输出满足相互制约条件的序列,为1时输出半相互制约条件的序列)。
 

Output

5
0 0 1 1 1
1 0 1 1 0
0 0 0 1 0
0 0 0 0 1
0 1 1 0 0
 

Sample Input

0
1 3 4 5 2

Sample Output

Hint

100%的数据,2<=n<=200


请不要提交,期待SPJ

Source