円環上で同じ値が隣接している場合，それらをまとめて一つにしても答えは変わりません．

また，\(1,2\) が隣接している場合，その \(2\) つをつなぎ，\(1\) を消しても答えは変わりません． 同様に，\(3,4\) が隣接している場合も，\(4\) を消すことができます．

上記の操作を可能な限り繰り返すことを，”正規化”と呼ぶことにします．

valid な木には，必ず次の条件を満たす辺が存在しています．

• その辺の \(2\) つの端点は円環上で隣接している．
• その辺の一方の端点は葉である．

よって，valid な木は，以下の操作を繰り返すことで得られることがわかります．

• 円環上で隣接しており，かつ辺で結べる \(2\) つの頂点を選ぶ．
• その \(2\) つを結ぶ．
• 一方の頂点を葉として選び，円環から消す．

正規化された状態に対し，上記の操作を \(1\) 度行い，更に正規化する，という一連の動作を考えます．

正規化された状態では，辺で結べる頂点のペアは，\(2,3\) が書かれたペアのみです． ここで，\(2\) を葉として消したとします． もともとの円環で \(\cdots,4,2,3,\cdots\) と値が並んでいた場合， \(2\) を消した後，\(4\) と \(3\) が隣接するので，正規化によって \(4\) が更に消えます． 結局，全体として見れば，\(4,2\) が消えることになります． 同様に，もともとの円環で \(\cdots,3,2,3,\cdots\) と値が並んでいた場合は，\(3,2\) が消えることになります．

\(3\) を葉として選ぶ場合も考えると，結局，一連の動作で消える頂点のペアは，\((2,3),(1,3),(2,4)\) のいずれかです．

上の操作を繰り返し，最終的に円環上に \(2,3\) のみが残れば，valid な木が構築できます．

以上より，次の必要条件が導かれます．

• \(A\) に含まれる \(1,2,3,4\) の個数を \(C_1,C_2,C_3,C_4\) とする．
• \(C_2>C_4\) かつ \(C_3>C_1\) が必要．

また，これが十分条件であることも確認できます． これは，\(1\) か \(4\) が円環上に残っている時，\((1,3)\) もしくは \((2,4)\) を消すような操作が必ず行えるためです．

以上の条件付けをそのまま実装すれば，\(O(N)\) 時間の解法が得られます．

解答例(c++)