1. 前計算と辺の発見

まず前計算として、初期頂点を根とする DFS 木を構成する。このとき Move をちょうど \(2M\) 回行えばよい（各辺を往復ちょうど 1 回ずつ通るため）。

各頂点の状態を次の 3 色で管理する：

• 色 1：未訪問
• 色 2：訪問済みであり、その部分木を現在探索中
• 色 3：訪問済みであり、その部分木の探索が終了

頂点番号は DFS の行きがけ順で適当に付与しておく。

現在頂点 \(u\) にいるとき、隣接頂点 \(v\) が色 2 であれば、DFS 木上で \(v\) は \(u\) の祖先である。

このとき、辺 \(e = (u,v)\) を使って Move し、移動先の色が 2 だった場合、辺 \(e\) が「発見された」と定義する。

ここで、DFS 木に含まれない任意の辺は、探索中にちょうど 1 回だけ発見される。

理由は次の通り：

• 任意の辺 \(u-v\) の端点は DFS 木上で必ず祖先・子孫関係にある
  
• 深い方の頂点を探索している時に、その祖先との辺がちょうど 1 回だけ観測される
  

したがって、各非木辺は一意に特定される。

---

2. もう一方の端点の特定方法

辺 \(e\) が発見されたとき、そのとき探索中だった頂点が片方の端点である。

したがって、もう一方の端点が「どの祖先か」を特定できればよい。

次の DFS を用いることで、「もう一方の端点の \(X\) 進数表記における第 \(k\) 桁」をすべての辺について特定できる。

アルゴリズム

1. DFS 木を行きがけ順に走査する。現在頂点を \(u\) とする。
   
2. \(u\) から子へ移動する直前に、\(u\) の色を「\(u\) の \(X\) 進数表記の \(k\) 桁目」に対応する色に設定する。
   
3. \(u\) を端点に持つと既に分かっている辺 \(e\) について、その辺を使った先の色を確認する。その色が「もう一方の端点の第 \(k\) 桁」の値である。
   

この DFS では、各辺はちょうど 2 回通られる。

---

3. 全端点の特定と計算量

色は 3 種類使えるため、\(3^5 = 243 \ge 200\) より、5 桁あれば最大 200 頂点を識別できる。

したがって、この DFS を 5 回（各桁について 1 回ずつ）実行すれば、すべての辺の両端点を特定できる。

Move 回数は、前計算の DFS に \(2M\) 回、各桁ごとの DFS にそれぞれ \(2M\) 回かかるため、\(2M \times (1 + 5) = 12M\) 回の Move で完了する。

AC コード (C++) : https://atcoder.jp/contests/joisc2016/submissions/73234551