题目描述

有 $N$ 支球队，已知部分比赛结果 $X\to Y$（$X$ 战胜 $Y$）。请给出一个与这些结果相符的、从第 $1$ 名到第 $N$ 名的完整排名，并判断这样的排名是否还有其他可能。

保证比赛结果符合某个排名：排名靠前的球队可以战胜排名靠后的球队。

输入格式

第一行一个整数 $N$，第二行一个整数 $M$。接下来 $M$ 行，每行两个整数 $X,Y$，表示 $X$ 战胜 $Y$。

输出格式

输出 $N+1$ 行：前 $N$ 行依次输出从第 $1$ 名到第 $N$ 名的球队编号；最后一行输出 0 表示排名唯一，输出 1 表示还存在其他符合条件的排名。

4
3
1 3
2 3
3 4

1
2
3
4
1

上面 2, 1, 3, 4 也符合比赛结果，因此最后一行是 1。

数据范围

$1\le N\le 5000$，$0\le M\le 10^5$；数据保证存在合法排名。

提示

比赛结果构成一张有向无环图。每轮选择当前入度为 $0$ 的球队：若某一轮同时有多支可选球队，合法排名就不唯一。

本题采用 Special Judge，任何符合比赛结果的完整排名都可以被接受，但最后一行的唯一性判断必须正确。