For each deck \(i\), let \(p_i\) be the deck containing the other card with \(A_{i,1}\) written on it, and consider the functional graph with edges drawn from vertex \(i\) to vertex \(p_i\). In the following, we identify vertices and decks (for example, we use expressions such as “decks that are leaves in the functional graph”).

Consider a deck \(i\) that is a leaf in the functional graph. Being a leaf means that \(A_i\) does not contain any of the integers written on the top card in the initial state. Therefore, the cards in deck \(i\) can be discarded in order from the top, and it is better to discard all of them in this case. If we repeat this from the leaf side, we can eventually discard the cards in the decks that are not in the cycle part of the functional graph.

Next, consider the decks in the cycle part of the functional graph. If we label the decks in the cycle part as \(1,2,\dots,n\) in the order within the cycle, then \(A_1,A_2,\dots,A_n\) have the following structure:

$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)$

Focusing only on the \((a_i,\dots,a_{i-1})\) part of each deck, we consider the integer sequence \(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)\) obtained by rearranging them, in the following cases in order:

• The case where there is an integer that appears only once in \(X\)
• The case where there are integers \(x\) and \(y\) in the positional relationship \(X=(\dots,x,\dots,y,\dots,x,\dots,y,\dots)\)
• The cases other than the above

[1] If there is an integer that appears only once in \(X\)

First, consider the situation where there is an integer \(x\) that appears only once in \(X\). Such an \(x\) can be assumed to be in \(A_n\). In this situation, the cards in deck \(n\) can be discarded until the card with \(x\) written on it is at the top. After discarding them in this way, we consider what happens when we recreate the functional graph. First, for \(i < n\), \(p_i\) remains \(p_i=i+1\). We divide the cases by the deck containing the other card with \(x\) written on it.

[1-1] If none of the decks \(1,2,\dots,n-1\) contain a card with \(x\) written on it

In this case, deck \(1\) is a leaf in the functional graph, and the cards in decks \(1,2,\dots,n\) can be discarded in order from the top.

[1-2] If it is included in deck \(k\ (k < n)\)

From the initial assumption, the card with \(x\) written on it in deck \(k\) is below the card with \(a_{k-1}\) written on it, and has the following structure:

$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)$

In this case, deck \(1\) is a leaf in the functional graph, and the cards in decks \(1,2,\dots,k-1\) can be discarded in order from the top. Decks \(k,k+1,\dots,n\) form a cycle, and \(a_{k-1}\) appears only once in the \((a_i,\dots,a_{i-1})\) part. Therefore, it can be inductively seen that by repeating this, the cards in decks \(k,k+1,\dots,n\) can eventually be discarded as well.

From the above, if there is an integer \(x\) that appears only once in \(X\), all cards in the decks in the cycle part can be discarded.

[2] If there are integers \(x\) and \(y\) in the positional relationship \(X=(\dots,x,\dots,y,\dots,x,\dots,y,\dots)\)

Note that neither \(x\) nor \(y\) is one of \(a_i\) (i.e., they are not at the top of a deck in the initial state).

[2-1] If there is a deck containing both \(x\) and \(y\)

It can be assumed that deck \(n\) contains both \(x\) and \(y\). If the cards in deck \(n\) are discarded until the card with \(x\) written on it is at the top, we have the following situation:

$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)$

First, deck \(1\) is a leaf, and the cards in decks \(1,2,\dots,j-1\) can be discarded in this order. Decks \(j,j+1,\dots,n\) form a cycle, but considering the existence of \(y\) in deck \(n\), they fall into the pattern in [1], so all the cards can be discarded.

[2-2] If \(x\) and \(y\) are in separate decks

If the cards in one of the decks containing a card with \(x\) written on it are discarded until the card with \(x\) written on it is at the top, we have the following situation:

$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)$

In this state, if we recreate the functional graph, deck \(1\) is a leaf, and the cards in decks \(1,2,\dots,j-1\) can be discarded in this order. Decks \(j,j+1,\dots,n\) form a cycle, but considering the existence of \(y\) in deck \(k\), they fall into the pattern in [1], so all the cards can be discarded.

[3] The cases other than [1] or [2]

When the operation is performed on decks \(1,2,\dots,n\), the functional graph turns into a cycle plus a path graph connected to it, and the \(X\) for the cycle part falls into case [3] again. After repeating this process, the final structure will be as follows, where the operation cannot be performed on the cycle part:

$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)$

The final remaining structure corresponds to a cycle on \(X\) formed by alternating between:

• moving to an adjacent term, and
• moving to a term with an equal value.

Also, for any cycle on \(X\) formed in this way, it is possible to perform the operation so that we end up with the above structure corresponding to that cycle on \(X\). This can be seen inductively from the fact that performing the operation on a deck containing a \(b_i\) that is not written on the top card of a deck can reduce the number of cards while keeping the cycle on \(X\) composed of \(b_i\).

Therefore, for each cycle on \(X\), we should compute the number of cards that will be left at the bottom, and choose the one with the smallest number of remaining cards.

The check for whether the situation falls into case [1] or [2], and the enumeration of cycles on \(X\) in case [3] can be done in \(O(M)\) time using stacks.

(Above is a modification of a translation by GPT-4.)