1406: 郁闷的记者

内存限制:256 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:24 解决:12

题目描述

你是一个体育报社的记者,你接受到一个艰难的任务:有N支足球队参加足球比赛,现在给你一些比赛的结果,需要你给出各支球队的排名,从1N

以下是给你的一些信息:

(1)  没有平局;

(2)  不同的球队排名不能相同;

(3)  对于所有满足1<=a<b<=n,第a名的球队一定可以打败第b名的球队。

给你部分比赛结果,要求给出排名,并且判断是否存在另一种排名方法满足给你的比赛结果。

输入

第一行输入N(1<=N<=5000),表示球队的数量,编号为1N。第二行输入M(1<=M<=100,000),表示给出的比赛场数,接下来M行,每行两个整数X_i,Y_i,表示X_i能打败Y_i

输出

 输出包含N+1行,前N行描述球队的排名,第i个数表示第i名的球队,第N+1行包含一个整数,如果为0表示不存在其他的排名方法,否则为1表示还有其他的排名方法。

样例输入 复制

4
5
1 2
3 1
3 2
3 4
4 1

样例输出 复制

3
4
1
2
0

提示

【样例输入输出】

Rank.in

Rank.out

4

5

1 2

3 1

3 2

3 4

4 1

3

4

1

2

0

3

2

2 1

2 3

2

1

3

1

 

【数据范围】

30%的数据 1<=N<=7,1<=M<=15

60%的数据1<=N<=100,1<=M<=2000

用cena测试,有多组解