操作を逆から見ることにします．

\(i \to A_i\) の辺を張ったグラフを考えます． \(i=N\) の操作を巻き戻すことが，このグラフをどう変化させるか考えます．

頂点 \(N\) に注目します． まず，頂点 \(N\) がサイクルに含まれているかどうかを考えます．

• 頂点 \(N\) がサイクルに含まれている場合：このサイクル上の頂点が，操作前に箱 \(N\) に入っていたボールに対応する．このサイクルを分解し，サイクル上の頂点から頂点 \(N\) へ辺を張る．
• 頂点 \(N\) がサイクルに含まれていない場合：適当なサイクルが，操作前に箱 \(N\) に入っていたボールに対応する．このサイクルを分解し，サイクル上の頂点から頂点 \(N\) へ辺を張る．ただし，箱 \(N\) は空だったことにして，何も変化させないことも許される．

どちらのケースでも，頂点 \(N\) に”子”(頂点 \(N\) へと辺を伸ばしている頂点であって，サイクルに含まれないもの)が存在した場合，操作の巻き戻しは不可能になり，答えが No であるとわかります．

頂点 \(N\) がサイクルに含まれていない場合，どのサイクルを分解するかで自由度がありますが，ここでは仮に，頂点 \(N\) の含まれる連結成分のサイクルを使うことにしましょう．

操作の巻き戻しをこの形に絞って考えた時，\(i=N,N-1,\cdots,1\) に対して巻き戻しを完了できる条件を考えてみます．

すると，十分条件として，各頂点 \(v\) について以下の性質が成り立つという条件が得られます．

• \(v\) の子を \(u_1,\cdots,u_k\) とおく．\(u_i\) の部分木内で番号最大の頂点を \(w_i\) とおく．ここで，\(v < w_i\) である．

実はこの条件は，もとの問題 (巻き戻しの操作の形を限定しない) における必要条件でもあります． よってこの条件をそのまま判定することでこの問題を解くことができます．

この条件が必要であることを示します． 条件を満たさない頂点 \(v\) とその子 \(u\) をとってきます． \(i=N,N-1,\cdots,v+1\) の操作をどうやって巻き戻しても，頂点 \(u\) の部分木には影響しません． そして \(i=v\) を考えると，\(v\) は子 \(u\) を持つことになるので巻き戻しに失敗します． これで必要性が示されました．

条件の判定は \(O(N)\) で行えます．

解答例(C++)

おまけ：valid な \(A\) の個数は \((2N-1)!!\) です．証明を考えてみてください．