どの人も高々 \(2\) 人としか隣り合うことはできません。したがって、条件の中に \(3\) 回以上登場する人がいた場合、答えは No です。この判定は \(O(N+M)\) で容易に行えます。

また、\((A_i,B_i)=(1,2),(1,3),(2,3)\) などのように、ループする条件がある場合も No です。この判定はUnion-FindやBFS, DFSなどを用いることで \(O(N+M)\) などで行なえます。

逆に、以上の \(2\) 条件に抵触しない場合、(実際に並べて確かめることなく！)答えは Yes となるため、この問題が解けました。

実装例(C++)