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