Subtask 1

By examining small cases, or by guessing, we can assume that there always exists a solution when there is exactly one unknown swap. The proof of this lies in the construction presented in subtask ~2~. This means that for all unknown swaps apart except for one, we can choose the swapped stones arbitrarily.

All that is left is to choose the final unknown swap. Since there are only three possible final swaps, we can check each of them by simulating through all moves in ~\mathcal{O}(M)~.

Time complexity: ~\mathcal{O}(M)~

Subtask 2

As in Subtask ~1~, we assign all unknown swaps except for one arbitrarily, such that there is only one unknown swap. We are no longer guaranteed that there are only three possible swaps, so we need a smarter algorithm.

Let ~X~ be the position of the stone just before the unknown swap, and let ~Y~ be the position that the stone needs to be in just after the unknown swap in order to end at ~B~. We can find ~X~ by simulating forward through the swaps, and find ~Y~ by simulating through the swaps in reverse order.

Then, if ~X \ne Y~, we can choose to swap ~X~ and ~Y~ in the unknown swap. Otherwise, we can just choose two distinct shells which are not equal to ~X~, and swap them instead.

Time complexity: ~\mathcal{O}(M)~