郁闷的记者

成绩 0 开启时间 2012年12月29日 星期六 15:35
折扣 0.8 折扣时间 2012年12月29日 星期六 15:35
允许迟交 是 关闭时间 2012年12月29日 星期六 15:35
输入文件 rank.in 输出文件 rank.out

【题目描述】

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

    以下是给你的一些信息：

    (1)没有平局；

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

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

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

【输入格式】

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

【输出格式】

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

【样例输入输出】

rank．in

rank．out

 4

5

1  2

 3  1

 3  2

 4  1

 3

 4

 1

 2

 O

 

3

 2

2  1

 2  3

2

 1

 3

 1

 

【数据范围】

30％的数据满足：l≤N≤7，1≤M≤15  

60％的数据满足：l≤N≤100，1≤M≤2000