簡易解説

何回かユウキ君式のシャッフルをすることによってデッキを初期状態に戻せます。
つまり、制約を満たしつつ-1を出力するようなテストケ―スは存在しません。

最初に初期状態に戻るまでコンピューターにシャッフルさせる事を考えます。
この方法だと小さい制約だと2秒以下で計算できますが、この制約だと必要なシャッフル数が$10^8$を超えるケースがいくつかあるのでTLEとなります。

次に、初期状態から何回シャッフルしたらデッキが初期状態に戻るのかを効率的に計算する方法を考えます。
それをするにあたって上から$i$番目のカード(初期状態では$i$)は何回シャッフルするとまた上から$i$番目の位置に戻るか考えます。
これは鳩ノ巣原理によって$N$回以下で戻ってくる事がわかります。また、$i$番目の カードが初めて上から$i$番目に戻ってくるような回数$Bi≧0$を考えた時、$Bi$の正の倍数回でも$i$番目に戻ってきます。 これには厳密でないな証明がいくつかありますが、数学的帰納法 を使って厳密に証明できます。

長さ$N$の数列$B = [B1,B2, ... , BN]$とした表した場合数列$B$の全部の数値で割り切れる最小の数のシャッフルをした場合、すべてのカードは初期位置に戻ります。なのでこれを$LCM(B1, B2,..., BN)$とした時、出力すべき答えは$(-M)mod(LCM(B1, B2,..., BN))$となります。

上記の解説文だけでは「鳩ノ巣原理で最悪$N$回で戻ってくるのをN回シミュレーションしたら$O(N^2)$でTLEする可能性がある」と考えた方もいるかと思われますが、$i$番目のカードが$Bi$の倍数回で元の位置に戻るなら元に戻るまでに行った事のある位置に最初あったカードも$Bi$の倍数回で元の位置に戻ります。 なので深さ優先探索をすることで数列$B = [B1,B2, ... , BN]$を求める部分は$O(N)$となり、十分高速です。 Pythonだとオーバーフローの考慮をしなくて良いですが、この数値は非常に大きなもの(最悪$10$の$100$乗以上)になる可能性があるため他の言語だと注意が必要となります。

更なる証明と考え方

この問題をグラフ問題に帰結する事を考えます。
ユウキ君式シャッフルは数列$A = [A1,A2, ... , An]$ が与えられた時、これを頂点$i$から頂点$Ai$へと向かう辺として表すことによってシャッフルの言動を有向グラフで表すことができます。(具体的に言うと、頂点$i$から$x$回辺をたどって到達した点$j$が初期状態から$x$回シャッフルした場合の カード$i$の位置になります。)

上記の用な有効グラフを作ったところで、制約に会った文の一つ「数列$A$には$1$から$N$の数字が各一回ずつ出現する」に注目します。
これはユウキ君式シャッフルを有効グラフとして表した場合：
・各頂点から出る辺は一つだけ
・各頂点へと向かう辺は一つだけ
と言う条件に言い換えられます。上記の条件から各カードは初期状態から1回以上シャッフルして元通りの位置に戻れること、また各カードは最小$1$枚、最大$N$枚の カードの「組」の一枚として決まったシャッフルのされ方をする事を示します。

まず各カードは初期状態から1回以上シャッフルして元通りの位置に戻れることを示します。上記の有向グラフ的に言うと、これは 「全ての$i$($1≦i≦N$)について頂点$i$を開始地点としたサイクルが存在する」事を証明すると同値です。

これを背理法によって証明します。
まず、「少なくとも一つの$i$($1≦i≦N$)について頂点$i$を開始地点としたサイクルが存在しない」場合、二つの可能性が考えられます:
・そもそもグラフに一つもサイクルがない
・サイクルはあるが、頂点$i$からたどり着く頂点$j$から始まる頂点$i$を含まないサイクルである
最初のケースが可能か考えます。頂点$i$から始めた場合、前提の通りで$k$個目の有向辺で$i$が含まれるサイクルを作らないようにするためには 頂点が少なくとも$k+1$個必要です。問題の条件から有効辺は$N$個存在するので、グラフには$N+1$個の頂点が必要となります。 したがって、最初のケースはあり得ません(サイクルが少なくとも一つは存在します)。

次のケースも
・各頂点から出る辺は一つだけ
・各頂点へと向かう辺は一つだけ
と言う前提と矛盾するため(頂点$j$に向かってる辺が二つ以上存在するようになります)、背理法で「全ての$i$($1≦i≦N$)について頂点$i$を開始地点としたサイクルが存在する」事が証明できました。 また、そのようなサイクルに入ってる「頂点の組」の集合$[S1, ..., Sk]$を考えた場合、$Si$に入ってる各頂点は$Si$の要素数の倍数回にて元の位置に戻る事がわかります。

このようなサイクル達への分解は
・DFS
・Union-Find
のどちらでも可能です。相当定数倍高速化が上手い高速言語の使い手の方は$O(N^2)$の方法でもギリギリ通せるかもしれません。

最後まで解説を読んでいただき、ありがとうございます。