問題文

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

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

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

入力

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

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

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

出力

$U1$
$\dots$
$UN$

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

サンプル

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

1
1
1
1
1
1

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