시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 57 | 42 | 36 | 72.000% |
あなたは JOI 新聞社の記者であり,スポーツ記事を担当している.
昨日までに,クロアチアでは,n 個のサッカーチームによる総当りのリーグ戦が 行われた.大会実行委員会は,試合結果と規定に基づき各チームに 1 位から n 位ま での順位をつけたようである.あなたには,一部の試合の勝敗とともに,次の情報 が伝えられた.
あなたは記事を作成するために,一部の試合の勝敗と,伝えられた情報 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 を出力せよ.
4 5 1 2 3 1 3 2 3 4 4 1
3 4 1 2 0
3 2 2 1 2 3
2 1 3 1