你是 JOI 报社的记者，负责体育报道。
截至昨天，克罗地亚举行了由 $n$ 支足球队参加的单循环联赛。大会执行委员会似乎已根据比赛结果和规定，给各支队伍评定了从第 $1$ 名到第 $n$ 名的名次。除了部分比赛的胜负结果外，你还得知了以下信息：
- 信息 $1$： 没有平局的比赛。
- 信息 $2$： 所有队伍的名次各不相同。
- 信息 $3$： 对于所有 $1 \le a < b \le n$，在第 $a$ 名的队伍与第 $b$ 名的队伍的比赛中，必定是第 $a$ 名的队伍获胜。
为了撰写报道，你决定根据部分比赛的胜负结果以及所获知的信息 $1$～$3$ 来推测排名表。
请编写一个程序，当输入给定部分比赛的胜负结果时，输出 $1$ 个符合所获知信息的排名表。同时，还需判定在输出的排名表之外，是否还存在符合所获知信息的其他排名表。
这里，排名表是指按第 $1$ 名到第 $n$ 名的顺序排列队伍所得的列表。
例子
例 1（符合信息的排名表只有 $1$ 个的情况）
设队伍数为 $4$，各队伍编号为 $1$ 到 $4$，且胜负结果由下表给出。
| $i \backslash j$ | $1$ | $2$ | $3$ | $4$ |
|---|---|---|---|---|
| $1$ | $-$ | $\circ$ | $\times$ | $\times$ |
| $2$ | $\times$ | $-$ | $\times$ | $?$ |
| $3$ | $\circ$ | $\circ$ | $-$ | $\circ$ |
| $4$ | $\circ$ | $?$ | $\times$ | $-$ |
当第 $i$ 行第 $j$ 列为 $\circ$ 时，表示在编号为 $i$ 的队伍与编号为 $j$ 的队伍的比赛中，编号为 $i$ 的队伍获胜。另外，为 $\times$ 时，表示编号为 $j$ 的队伍获胜。$?$ 表示未给出胜负结果。
此时，符合所获知信息的排名表只有如下 $1$ 个：
- 第 $1$ 名：编号 $3$ 的队伍
- 第 $2$ 名：编号 $4$ 的队伍
- 第 $3$ 名：编号 $1$ 的队伍
- 第 $4$ 名：编号 $2$ 的队伍
例 2（符合信息的排名表有多个的情况）
设队伍数为 $3$，各队伍编号为 $1$ 到 $3$，且胜负结果由下表给出。
| $i \backslash j$ | $1$ | $2$ | $3$ |
|---|---|---|---|
| $1$ | $-$ | $\times$ | $?$ |
| $2$ | $\circ$ | $-$ | $\circ$ |
| $3$ | $?$ | $\times$ | $-$ |
此时，符合所获知信息的排名表有如下 $2$ 个：
- 第 $1$ 名：编号 $2$ 的队伍，第 $2$ 名：编号 $1$ 的队伍，第 $3$ 名：编号 $3$ 的队伍
- 第 $1$ 名：编号 $2$ 的队伍，第 $2$ 名：编号 $3$ 的队伍，第 $3$ 名：编号 $1$ 的队伍
输入
第 $1$ 行写有足球队的数量 $n$。各支队伍编号为 $1$ 到 $n$。
第 $2$ 行写有给定的比赛胜负结果的数量 $m$。
从第 $3$ 行到第 $m + 2$ 行表示比赛的胜负结果。每行包含以空格分隔的 $2$ 个整数 $i, j$，表示编号为 $i$ 的队伍战胜了编号为 $j$ 的队伍。
$n, m$ 满足 $1 \le n \le 5000$，$1 \le m \le 100000$。
在评测所用的测试数据中，占总分 $30\%$ 的数据满足 $1 \le n \le 7$，$1 \le m \le 15$。此外，占总分 $60\%$ 的数据满足 $1 \le n \le 100$，$1 \le m \le 2000$。
输出
输出由 $n + 1$ 行组成。
从第 $1$ 行到第 $n$ 行的 $n$ 行中，输出符合所获知信息的排名表。在第 $i$ 行（$1 \le i \le n$）输出第 $i$ 名的队伍编号。
在第 $n + 1$ 行输出一个整数，表示在输出的排名表之外是否还存在符合所获知信息的排名表：若不存在则输出 $0$，若存在则输出 $1$。
样例输入与输出
样例输入 1
与例 $1$ 对应的输入与输出如下。
4 5 1 2 3 1 3 2 3 4 4 1
样例输出 1
3 4 1 2 0
样例输入 2
与例 $2$ 对应的输入数据如下。
3 2 2 1 2 3
对于该输入数据，可以考虑以下 $2$ 种输出数据，输出其中任意一种均可。
样例输出 2
2 1 3 1
2 3 1 1