最悪の記者

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

昨日までに，クロアチアでは，n 個のサッカーチームによる総当りのリーグ戦が 行われた．大会実行委員会は，試合結果と規定に基づき各チームに 1 位から n 位ま での順位をつけたようである．あなたには，一部の試合の勝敗とともに，次の情報 が伝えられた．

• 情報 1 引き分けの試合はなかった．
• 情報 2 全てのチームに異なる順位がついた．
• 情報 3 全ての 1 ≤ a < b ≤ n に対し，a 位のチームと b 位のチームの試合において， 必ず a 位のチームが勝利した．

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

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

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

1 行目には，サッカーチームの個数 n が書かれている．各チームには，1 から n ま での番号が付けられている．

2 行目には，与えられた試合の勝敗の個数 m が書かれている．

3 行目から m + 2 行目は試合の勝敗を表す．各行は空白で区切られた 2 つの整数 i, j を含み，番号 i のチームが番号 j のチームに勝利したことを表す．

n, m は 1 ≤ n ≤ 5000, 1 ≤ m ≤ 100000 をみたす．

出力ファイルは n + 1 行からなる．

1 行目から n 行目までの n 行には，伝えられた情報に適合する順位表を出力せよ． i 行目 (1 ≤ i ≤ n) に i 位のチームの番号を出力せよ．

n + 1 行目には，出力した順位表以外に，伝えられた情報に適合する順位表が存在 するかどうかを表す整数を出力せよ．もし存在しなければ 0 を，存在する場合は 1 を出力せよ．