swap 操作より，与えられたグラフで連結であるような値の集合は自由に入れ替えることができます．この連結成分を 色 として捉えることにします． reverse 操作は \(P_l\) と \(P_r\) が同じ色であるような \((l, r)\) を選ぶことになりますが，同じ色であれば操作ができるとしてしまって良いです．(操作ができる要素のペアを swap で \(P_l\) と \(P_r\) に持って来て，reverse をし，swap を元に戻せば実現可能)

すると，この問題は以下のように言い換えられます．

長さ \(N\) の数列 \(P\) があり，各要素には色が付いている． あなたは以下の操作を好きなだけできる．

• 同じ色である \(2\) 要素を選び，swap する．
• 同じ色である \(2\) 要素を選び，その間を reverse する．

さて，reverse 操作に注目すると，「隣接する要素の組」の集合はほとんど変わりません．さらに，「新たに隣接しなくなる要素の組」と「新たに隣接する要素の組」では，色が変化していません．

そこで，色を頂点とし，隣接する色の組を辺とするグラフを考えます． \(P_1\) の色を \(s\)，\(P_N\) の色を \(t\) とすると，\(P\) はグラフ上の \(s-t\) Eularian trail として表現することができ，reverse 操作は，trail の中の circuit の部分を reverse することに対応します．

この reverse 操作でどのような trail が作れるかをいくつかのケースで考えると，任意の \(s-t\) Eularian trail が作成可能であると予想できます．これは実際正しいです．

したがって，以下の問題が解ければ良いです．

\(N-1\) 辺の連結無向グラフが与えられる． グラフの \(s-t\) Eularian trail を任意に取り，それを頂点の列とみなし，頂点 \(i\) の \(j\) 回目の出現を整数 \(C[i][j]\) に置き換える．( \(C[i][j]\) は distinct で，各 \(C[i]\) は単調増加)

このようにして得られる列のうち，辞書順最小のものを求めよ．

これは，Eularian trail を求める典型的なアルゴリズムを，進む先を貪欲に選ぶように変更することで求められます．

これを単に実装すると \(\Theta(N^2)\) 時間かかってしまうため，高速化が必要です．

これは，次数が \(\Theta(\sqrt{N \log N})\) や \(\Theta(\sqrt{N})\) より大きい頂点と小さい頂点で処理を分けることにより，\(O(N \sqrt{N \log N})\) 時間や \(O(N\sqrt{N})\) 時間になります．

実装では，辺に番号を付け，多重辺をまとめるのではなく，HashSet でグラフを管理すると (低速になりますが) 実装が簡潔になります．