\(N\) 個の箱を頂点とし各箱 \(i\) から箱 \(P_i\) に有向辺を張って得られる有向グラフ \(G_P\) を考えます． 同様に，\(N\) 個の箱を頂点とし，各箱 \(i\) から箱 \(Q_i\) に有向辺を張って得られる有向グラフ \(G_ Q\) を定義します．

\(P, Q\) は順列なので，\(G_P, G_Q\) の各連結成分はサイクルをなします． \(G_P, G_Q\) における，\(X\) を含むサイクルをそれぞれ \(C_P, C_Q\) とします． \(C_P\) の外にある赤いボールは \(X\) に移ることはないので，そのようなボールがある場合は \(-1\) を出力します． \(C_Q\) の外に青いボールがある場合も同様です． 以下，そうではない場合を考えます．

全ての赤いボールを \(X\) に移すには，\(C_p\) 上の赤いボールのうち，\(X\) までの距離（\(X\) に到達するまで有向辺を向きに沿って辿るときの，辿る有向辺の本数）が最も遠いものの \(1\) つ（ \(\rho\) とする）のみに注目し，ボール \(\rho\) を箱 \(X\) に移すことだけを考えれば十分です． なぜなら，\(\rho\) を \(X\) まで移動させる過程で，\(\rho\) の通り道にある他の赤いボールも \(\rho\) に付随して \(X\) まで移動させられるからです．青いボールについても同様です．

よって，下記の状況を考えれば十分です．

• 赤いボールが箱 \(a_1\) のみに入っており， \(G_P\)上で \(a_1\) から \(X\) へのパス \(a_1 \to a_2 \to \cdots \to a_{|A|} \to X\) が存在する．
• 青いボールが箱 \(b_1\) のみに入っており，\(G_Q\) 上で \(b_1\) から \(X\) へのパス \(b_1 \to b_2 \to \cdots \to b_{|B|} \to X\) が存在する．

このとき，箱 \(I_1, I_2, \ldots, I_{|I|}\) に対してこの順に操作を行った結果，両方のボールが箱 \(X\) に入っている状態であるためには，操作列 \(I = (I_1, I_2, \ldots, I_{|I|})\) が \(A = (a_1, a_2, \ldots, a_{|A|})\) と \(B = (b_1, b_2, \ldots, b_{|B|})\) の両方を連続とは限らない部分列として含む（かつ，\(X\) を含まない）ことが必要十分です． そのような操作列 \(I\) で最短なものの長さは， \(A\) と \(B\) の最長共通部分列（ LCS ）の長さを \(L\) として，\(|A| + |B| - L\) です．

\(A\) と \(B\) の LCS は，\(A = (1, 2, \ldots, |A|)\) となるように \(N\) 個の全ての箱の番号 \(1, 2, \ldots, N\) を振り直す（それに伴って \(b_1, b_2, \ldots, b_{|B|}\) も適切に変更する）ことで， \(B\) の最長増加部分列（ LIS ）として \(O(N\log N)\) 時間で求められます．