题目描述

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

以下是给你的一些信息：

1. 没有平局；
2. 不同的球队排名不能相同；
3. 对于所有满足 $1 \le a < b \le N$，第 $a$ 名的球队一定可以打败第 $b$ 名的球队。

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

输入格式

第一行输入 $N$，表示球队的数量，编号为 $1$ 到 $N$。

第二行输入 $M$，表示给出的比赛场数。

接下来 $M$ 行，每行两个整数 $X_i$，$Y_i$，表示 $X_i$ 球队能打败 $Y_i$ 球队。

输出格式

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

3
2
2 1
2 3

2
1
3
1

提示

【数据范围】

• $30\%$ 的数据满足：$1 \le N \le7$，$1 \le M \le 15$；
• $60\%$的数据满足：$1 \le N \le 100$，$1 \le M \le 2 \times 10^3$；
• $100\%$ 的数据满足：$1 \le N \le 5 \times 10^3$，$1 \le M \le 10^5$。

本题已加入 Special Judge。

• 如果输出的最后一行错误将会提示 Your decide is wrong!；
• 如果存在多种排名情况，排名错误将会提示 Wrong ranks!；
• 如果情况固定且您的答案错误将会提示 In line X,Your ans is wrong:expected = X,found = Y。