ここにtesterの解説を書きます．


想定解はUnion-Find Algorithmを問題用に改造したものです．


Union-Findとは，次のような操作が出来るデータ構造です．

  union操作(x,y): xが入っている集合とyが入っている集合を結合する．
  find判定(x,y) : xとyが同じ集合に入っているかどうか判定する．

ここではUnion-Findの実装の解説はしないので，蟻本81ページや他ウェブサイトを参照してください．
http://www.prefield.com/algorithm/container/union_find.html


『Union-Findを貼るだけ問題』のように見えますが，
Union-Findの実装は計算量をなるべく減らすため，少ない方にマージしようとします．

しかし問題文では『猿の群れは数が多い方にマージされる』的な何かが書かれているので，
union操作の実装を題意に合わせるよう書き直す必要があります．


あとはシミュレートするだけです．


最悪計算量のオーダーは見積もれていないのでかしこーい人お願いします．