各山札 \(i\) について、\(A_{i,1}\) が書かれたもう一枚のカードを含む山札を \(p_i\) とし、頂点 \(i\) から頂点 \(p_i\) へ辺を張った functional graph を考えます。以下では頂点と山札を同一視します（例えば「functional graph において葉である山札」などといった表現を用います）。

functional graph で葉である山札 \(i\) を考えます。葉であるということは \(A_i\) は初期状態において一番上のカードに書かれている整数をいずれも含みません。よって山札 \(i\) のカードは上から順にすべて捨てきることができ、この場合は捨てきったほうが得です。これを葉側から繰り返すと、最終的には functional graph のサイクルの部分以外の山札のカードは捨てきることができます。

次に functional graph でサイクル部分の山札を考えます。サイクル部分の山札をサイクルの順に山札 \(1,2,\dots,n\) とすると、 \(A_1,A_2,\dots,A_n\) は以下のような構造となっています。

$A_1 = (a_1,\dots,a_n,\dots)$
$A_2 = (a_2,\dots,a_1,\dots)$
$A_3 = (a_3,\dots,a_2,\dots)$
$\vdots$
$A_n = (a_n,\dots,a_{n-1},\dots)$

各山札の \((a_i,\dots,a_{i-1})\) の部分にのみ着目し、これらを組み替えて得られる整数列 \(X=(a_n,\dots,a_{n-1},a_{n-1},\dots,a_{n-2},a_{n-2},\dots,a_{n-3},\dots,a_1,\dots,a_n)\) について、

• \(X\) に一度しか登場しない整数が存在する場合
• \(X=(\dots,x,\dots,y,\dots,x,\dots,y,\dots)\) という位置関係にある整数 \(x,y\) が存在する場合
• 上記以外の場合

の順に考えます。

[1] \(X\) に一度しか登場しない整数がある場合

まず \(X\) のなかに \(1\) 回しか登場しない整数 \(x\) が存在する状況を考えます。そのような \(x\) は \(A_n\) にあるとしてよいです。このような状況では山札 \(n\) のカードは \(x\) が書かれたカードが一番上になるまで捨て続けることができます。そのように捨て続けた後、 functional graph をつくりなおすとどうなるか考えます。まず \(i < n\) のとき \(p_i\) は \(p_i=i+1\) のままです。 \(x\) が書かれたもう一枚のカードを含む山札によって場合分けします。

[1-1] 山札 \(1,2,\dots,n-1\) のいずれも \(x\) が書かれたカードを含まない場合

このとき、functional graph では山札 \(1\) が葉になっており、山札 \(1,2,\dots,n\) の順に山札のカードを上から捨てきることができます。

[1-2] 山札 \(k\ (k < n)\) に含まれる場合

最初の仮定から、山札 \(k\) において \(x\) が書かれたカードは \(a_{k-1}\) が書かれたカードより下側にあり、以下のような構造になっています。

$A_1 = (a_1,\dots,a_n,\dots)$
$A_2 = (a_2,\dots,a_1,\dots)$
$A_3 = (a_3,\dots,a_2,\dots)$
$\vdots$
$A_k=(a_k,\dots,a_{k-1},\dots,x,\dots)$
$\vdots$
$A_n = (x\dots,a_{n-1},\dots)$

このとき、 functional graph において山札 \(1\) は葉になっており、山札 \(1,2,\dots,k-1\) の順に山札のカードを上から捨てきることができます。山札 \(k,k+1,\dots,n\) はサイクルになっており、 \(a_{k-1}\) は \((a_i,\dots,a_{i-1})\) の中で \(1\) 回しか登場しない整数になっています。よってこれを繰り返すことで最終的に山札 \(k,k+1,\dots,n\) のカードも捨てきることができるのが帰納的にわかります。

以上より \(X\) に一度しか登場しない整数 \(x\) が存在する場合、サイクル部分の山札のカードはすべて捨てきることができます。

[2] \(X=(\dots,x,\dots,y,\dots,x,\dots,y,\dots)\) という位置関係にある整数 \(x,y\) が存在する場合

\(x,y\) は \(a_i\) のいずれでもない（すなわち、初期状態で山札の一番上にはない）ことに注意します。

[2-1] \(x,y\) を両方とも含む山札が存在する場合

山札 \(n\) が \(x,y\) を両方とも含むとしていいです。山札 \(n\) のカードを \(x\) が書かれたカードが一番上になるまで捨てると以下のようになります。

$A_1 = (a_1,\dots,a_n,\dots)$
$\vdots$
$A_i = (a_i,\dots,y,\dots,a_{i-1},\dots)$
$\vdots$
$A_j = (a_j,\dots,x,\dots,a_{j-1},\dots)$
$\vdots$
$A_n = (x\dots,y\dots,a_{n-1},\dots)$

まず山札 \(1\) が葉になっており、山札 \(1,2,\dots,j-1\) のカードはこの順に捨てきることができます。山札 \(j,j+1,\dots,n\) はサイクルになっていますが、山札 \(n\) の \(y\) の存在を考えると [1] のパターンに該当するので、すべてのカードを捨てきることができます。

[2-2] \(x,y\) がすべて別の山札にある場合

\(x\) が書かれたカードを含む山札の \(1\) つについて、\(x\) が書かれたカードが一番上になるまでカードを捨てると以下のようになります。

$A_1 = (a_1,\dots,a_n,\dots)$
$\vdots$
$A_i = (a_i,\dots,y,\dots,a_{i-1},\dots)$
$\vdots$
$A_j = (a_j,\dots,x,\dots,a_{j-1},\dots)$
$\vdots$
$A_k=(a_k,\dots,y,\dots,a_{k-1},\dots)$
$\vdots$
$A_n = (x\dots,a_{n-1},\dots)$

この状態で functional graph を作り直すと、まず山札 \(1\) が葉になっており、山札 \(1,2,\dots,j-1\) のカードはこの順に捨てきることができます。山札 \(j,j+1,\dots,n\) はサイクルになっていますが、山札 \(k\) の \(y\) の存在を考えると [1] のパターンに該当するので、すべてのカードを捨てきることができます。

[3] [1][2] 以外の場合

山札 \(1,2,\dots,n\) に対して操作を行うと functional graph はサイクル + サイクルにつながる直線グラフに変化し、サイクル部分に対する \(X\) は再び [3] の場合に該当します。操作を繰り返すと最終的に以下のような構造になってサイクル部分に対する操作が不可能になります。

$B_1 = (b_1,b_n,\dots)$
$B_2 = (b_2,b_1,\dots)$
$B_3 = (b_3,b_2,\dots)$
$\vdots$
$B_m = (b_m,b_{m-1},\dots)$

最終的に残る構造は \(X\) 上で

• 隣の項に移動する
• 同じ整数の項に移動する

を交互に繰り返してできる \(X\) 上のサイクルに対応します。

また、このようにしてできる任意の \(X\) 上のサイクルについて、最終的に \(X\) 上のサイクルに対応した上記の構造になるように操作することができます。これは山札で一番上のカードに書かれていない \(b_i\) を含む山札に操作すると、カードの枚数を減らしつつ \(b_i\) からなる \(X\) 上のサイクルを残せることから帰納的にわかります。

よって各 \(X\) 上のサイクルについて下側に残る枚数を計算してこれが最小のものを選べばいいです。

[1][2] に該当するかのチェックや[3]での \(X\) 上のサイクルの列挙は stack を用いることで \(O(M)\) でできます。