시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB57423672.000%

문제

あなたは 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 を出力せよ.

예제 입력 1

4
5
1 2
3 1
3 2
3 4
4 1

예제 출력 1

3
4
1
2
0

예제 입력 2

3
2
2 1
2 3

예제 출력 2

2
1
3
1