你是 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