最悪の記者

問題

あなたは JOI 新聞社の記者であり，スポーツ記事を担当している．

昨日までに，クロアチアでは，n 個のサッカーチームによる総当りのリーグ戦が行われた．大会実行委員会は，試合結果と規定に基づき各チームに 1 位から n 位までの順位をつけたようである．あなたには，一部の試合の勝敗とともに，次の情報が伝えられた．
情報 1 引き分けの試合はなかった．
情報 2 全てのチームに異なる順位がついた．
情報 3 全ての 1 ≤ a < b ≤ n に対し，a 位のチームと b 位のチームの試合において，必ず a 位のチームが勝利した．

あなたは記事を作成するために，一部の試合の勝敗と，伝えられた情報 1 3 をもとに，順位表を推測することにした．

入力として一部の試合の勝敗が与えられたとき，伝えられた情報に適合する順位表を 1 つ出力するプログラムを作れ．また，出力した順位表以外に，伝えられた情報に適合する順位表が存在するかどうかも判定せよ．

ここで，順位表とは 1 位から n 位の順にチームを並べたもののことをいう．

例

例1 (情報に適合する順位表が 1 つしかない場合)

チーム数が4で，各チームに1から4までの番号が付けられており，勝敗が次の表で与えられていたとする．

i 行 j 列が○のときは，番号 i のチームと番号 j のチームの試合において，番号 i のチームが勝利したことを意味する．また，×のときは，番号 j のチームが勝利したことを意味する．? は勝敗が与えられていないことを意味する．このとき，伝えられた情報に適合する順位表は次の 1 つしかない

1 位 番号 3 のチーム 2 位 番号 4 のチーム 3 位 番号 1 のチーム 4 位 番号 2 のチーム

例2 (情報に適合する順位表が複数存在する場合)

チーム数が3で，各チームに1から3までの番号が付けられており，勝敗が次の表で与えられていたとする．

このとき，伝えられた情報に適合する順位表は，次の 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 ≤ n ≤ 5000, 1 ≤ m ≤ 100000 をみたす．

採点の際に用いるテストデータのうち，30% は 1 ≤ n ≤ 7, 1 ≤ m ≤ 15 をみたす．また，60% は 1 ≤ n ≤ 100, 1 ≤ m ≤ 2000 をみたす．

出力

出力は n + 1 行からなる．

1 行目から n 行目までの n 行には，伝えられた情報に適合する順位表を出力せよ．

i 行目 (1 ≤ i ≤ 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

---