ユニオン PHP編（paizaランク B 相当）

この問題ではユニオンファインド木における「ユニオン」をやってみましょう。

長さ n の数列 A を考え、数列 A の初期値を [0, 1, ..., n-1] とします。A の i 番目 (0 ≦ i ≦ n-1) の要素 A_i は整数 i の親を表しています。

ここで、ある整数 p の親を順々にたどっていった、p の祖先（または p 自身）である q について、A の q 番目の要素が q であるとき「 p は q の根である」と定義します。つまり、A の初期値では、すべての i (0 ≦ i ≦ n-1) において、i 自身が根となっています。

整数の組 (a,b) が合計 q 組与えられます。(a_j, b_j) (1 ≦ j ≦ q) に対して a_j の根を root(a_j)、b_j の根を root(b_j) として、次の操作を与えられた順番に処理し、最後に処理がすべて終了したあとの数列 A を出力してください。

root(a_j) と root(b_j) が同じでないなら、root(b_j) の親を root(a_j) とする。
同じならば何もしない。

ただし、p の根 root(p) は、p を入力として root(p) を返す次の関数 find を用いて求めてください。（この関数で求めない場合、処理終了後の数列 A が正しく出力されない可能性があります。）

def find(p)
  if p == A_p then
    return p
  else
    return find(A_p)
  end if

A_p は数列 A の p 番目の要素です。

ユニオンファインド木では同じ根を持つ要素たちを同じグループとみなして管理します。上の操作のように、別の根を持つ、別のグループの要素たちの根を同じにして同一グループとする操作を一般的にユニオンと言います。