P15405 [NOISG 2026 Prelim] Magic Trick (No testdata yet)

A new format of cards has been released. The value of each card is a base64 string of length $k$. The character set is: {#, \$, 0-9, A-Z, a-z}. There are $n = 64^k$ cards in total, and each string appears exactly once. The sealed new deck is sorted in lexicographical order from smallest to largest. Definition: a string $s$ is lexicographically greater than $t$ if and only if there exists a position $i$ such that $s_1 = t_1, \ldots, s_{i-1} = t_{i-1}$ and $s_i > t_i$. The shuffle is repeated infinitely many times. Each shuffle is performed as follows: 1. Split the deck into two halves: the first half is positions $1 \sim n/2$, and the second half is positions $n/2+1 \sim n$ (the internal order of each half remains unchanged). 2. Starting from the first half, take cards alternately from the two halves. If before shuffling the positions are numbered $1 \sim n$, then after one shuffle the order becomes $\langle 1, \frac{n}{2} + 1, 2, \frac{n}{2} + 2, \ldots, \frac{n}{2}, n \rangle$. There are $m$ tricks. The $i$-th trick requires that the card with value $x_i$ ends up at the position where the card with value $y_i$ is in the original sealed deck. Find the minimum number of shuffles needed to meet the condition. Output $0$ if it is already satisfied initially; output $-1$ if it can never be satisfied.

- The first line contains two integers $k, m$. $(1 \le k, m \le 1000)$. - The next $m$ lines each contain two strings $x_i, y_i$, both of length $k$. All strings use only the 64 characters above.

For each trick, output one line with an integer: the number of shuffles needed for the condition to be satisfied for the first time; if it is impossible, output $-1$.

### Constraints - $1 \le k, m \le 1000$ ### Subtasks |Subtask ID|Properties|Score| |:-:|:-:|:-:| |1|$k \le 8$|20| |2|$k, m \le 100$|30| |3|No special constraints|50| Translated by ChatGPT 5