完璧な配列を構築する
あなたはコンピュータサイエンティストの友人が進めている研究プロジェクトを手伝っています。プロジェクトでは、特定の制約を満たす配列を見つける必要があります。具体的には、長さ
n の配列 a に対して、p 組のインデックス (i, j) が与えられます。各組 (i, j) は「 が より小さい」という制約を示します。あなたのタスクは、与えられたすべての制約を満たす配列 a を見つけることです。配列
a に含まれる整数は、1 以上 以下でなければなりません。入力
入力の最初の行には、
n (2 ≤ n ≤ ) と p (1 ≤ p ≤ ) の 2 つの整数が与えられます。n は配列 a の長さ、p は与えられるペアの数を示します。続く p 行のそれぞれに、i と j (1 ≤ i < j ≤ n) の 2 つの整数がスペース区切りで与えられます。これは「 < 」という制約を表すインデックスのペアです。出力
すべての制約を満たす配列
a を見つけられた場合、a の要素を空白区切りで n 個出力してください。各要素は必ず 1 以上 以下の整数でなければなりません。もし複数の解が存在するときは、そのうちのいずれかを出力して構いません。もし、そのような配列を見つけることができない場合は、
Impossible と出力してください。例
入力 | 出力 |
4 2
1 2
4 1 | 2 3 4 1 |
5 5
1 2
2 3
3 4
5 4
2 5 | 2 4 6 8 5 |
3 3
1 2
2 3
3 1 | Impossible |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB