No.556 仁義なきサルたち

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 100
作問者 : horiesinitihoriesiniti / テスター : mai(舞葉)mai(舞葉)

0 ProblemId : 1213 / 出題時の順位表

問題文

この島にはN匹の不良サルがいる。

一匹ごとに1~Nまでの序列が付いており序列一位が1、序列i位がi,序列最下位N位がNの番号が付いている。 同じ序列のサルはいない。 人間たちがサルに組織の概念を教えた結果島でサルたちの組織争いが始まった。

最初サルたちは一匹一匹が独立した存在で自分自身のボスでありメンバー数一匹のチームである。 別チームの2匹のサルがケンカすると、互いのチームのボスが子分全員を引き連れて勝負となる、数の多いほうのチームが勝つ、頭数が同じ場合序列の高い(序列1位か1位に近い)ほうのボスが勝ちとなり負けたチームは勝ったチームに吸収される。 勝ったチームのボスはボスのままである。 同じチームのサルがケンカした場合はボスが仲裁するかボスが勝つので何も起こらない。 ケンカのデータが与えられる。 全てのケンカを終わった後の全サルのボスを番号1からNまで順番に答えよ。 自身がボスなら自身の番号を返すこと。

入力

$N$ $M$
$A1$ $B1$
$\dots$
$AM$ $BM$

Nは猿の個体数である。
2 <= N<=10000
サルには番号が付いており1番のサルが序列1位でi番のサルが序列i位である。 よって猿の序列に関するデータはない。

Mはケンカの回数である。
1 <= M<=N
1 <= Ai,Bi <= N
Ai BiはサルAiとBiがケンカをしたというデータである,Ai,Biとも猿の番号であり数字である。 ケンカが起こった順番に与えられる。 AiとBiは同じでないとする。

出力

$U1$
$\dots$
$UN$

出力は各サルの番号1~番号Nまでの各サルのボスを順番に一行ずつ出力せよ。 出力の番号Uiは番号iのサルのボスを出力すること。

最後に改行してください。

サンプル

サンプル1
入力
6 6
2 1
1 4
3 5
5 6
3 6
3 4
出力
1
1
1
1
1
1

1 2 4というチームと3 5 6というチームができる。 3と4がケンカになったので,ボスの1と3が出張るも同数、序列の高い1が全部のボスになった。

サンプル2
入力
11 8
1 4
2 3
4 3
5 9
6 8
8 10
8 11
5 10
出力
1
1
1
1
6
6
7
6
6
6
6

1 2 3 4というチームと5 9というチームと6 8 10 11というチームができる。 最後に5 9チームと6 8 10 11チームがケンカするが,6 8 10 11チームのほうが頭数が多いので6が5 9の新しいボスとなる。

提出ページヘ