順列 \(P\) に対して \(P^k = (1,2,\dots,N)\) を満たす最小の正整数 \(k\) を \(ord(P)\) と表記します。また、\(Q\) の満たすべき条件をただ条件と呼びます。

条件を満たす \(Q\) が存在するとします。そのような \(Q\) を \(1\) 個取ってきます。各 \(i\) に対して、\(Q^k = P_i\) を満たす最小の正整数 \(k\) を \(k_i\) と置きます。

まず、各 \(i\) に対して \(ord(Q)\) は \(ord(P_i)\) の倍数です。つまり、\(ord(Q)\) は \(L = \mathrm{lcm}(ord(P_1),ord(P_2),\dots,ord(P_M))\) の倍数です。

更に、\(ord(Q) = L\) を満たす \(Q\) の存在性が証明できます。もし今 \(ord(Q) = cL(c \ge 2)\) と表されるとします。このとき、\(k_i\) は \(\frac{cL}{ord(P_i)}\) の倍数です。\(L \bmod ord(P_i) = 0\) に注目すると、\(ord(Q^c) = L\) かつ \(Q^c\) は条件を満たします。よって \(ord(Q) = L\) を満たす \(Q\) の存在が証明出来ました。以降これを仮定します。

\(L = \prod_{i=1}^{m} p_i^{e_i}\) と素因数分解できたとします。\(L\) の定義から、\(ord(P_j) \bmod p_i^{e_i} = 0\) を満たす \(P_j\) が存在します。ここで、\(e'_i = \frac{ord(P_j)}{p_i^{e_i}},R_i = P_j^{e'_i}\) と定義します。このように定義すると、\(ord(R_i) = p_i^{e_i}\) となります。つまり、\(R_i = Q^k\) と表すと、\(k = \frac{d_iL}{p_i^{e_i}}(d\) は \(p_i\) で割り切れない整数)となります。

すると、\(R' = \prod_{i=1}^{m} R_i\) は条件を満たします。証明をします。\(R' = Q^r\) とします。\(gcd(r,L) = 1\) を満たせば、\(R'\) は条件を満たします。ここで、\(\displaystyle r = \sum_{i=1}^{m} \frac{d_iM}{p_i^{e_i}}\) です。\(gcd(r,L) = 1 \iff\) 全ての \(i\) に対して \(r \bmod p_i \neq 0\) ですが、これは \(d_i \bmod p_i \neq 0\) から簡単に証明できます。

ところで、\(R'\) 自体を構築するのは \(Q\) の存在性に関わらず可能です。\(L\) を素因数分解された形で計算し、\(L\) の素因数 \(p_i\) に対して \(R_i\) を計算し、それらの積を取ればよいです。

こうして構築した \(R'\) に対して \(R'^k = P_i\) を満たす \(k\) が存在するか判定すればよいですが、これは各サイクルに注目すると \(k \bmod a = b\) という条件がいくつか出てくるためこれらを同時に達成できるかを判定すればよく、\(1\) 個の \(P\) あたり \(\mathrm{O}(N)\) で判定できます。

\(R'\) を構築する部分に対しては、\(L\) を \(\mathrm{O}(NM)\) で求め、\(R_i,R'\) を \(\mathrm{O}(Nm)\) で求めればよいです。よって、全体で \(\mathrm{O}(N^2 + NM)\) で解くことが出来ます。

実装例：https://atcoder.jp/contests/arc228/submissions/78749656

ここからはおまけですが、この問題には乱択解法も存在します。

\(x_i\) をランダムに取り、\(Q = \prod_{i=1}^{N} P_i^{x_i}\) を計算し、\(Q\) が条件を満たすか判定します。\(Q\) が条件を満たせば出力、満たさないならば \(C\) 回までは繰り返します。

もし条件を満たす \(Q\) が存在しない場合はこのアルゴリズムは必ず No を出力します。存在する場合、\(1\) 回 \(Q\) を計算したときの成功確率を考えます。\(R = Q^k\) となったとしましょう。\(gcd(k,L) = 1 \iff\) 全ての \(i\) に対して \(k \bmod p_i \neq 0\) となり、\(x_i\) をランダムに取っているため \(k \bmod p_i = 0\) となる確率は \(\frac{1}{p_i}\) です。つまり、総和が \(N\) 以下である素数の集合 \(P=\lbrace p_1,p_2,\dots,p_c \rbrace\) に対する \(\prod_{i=1}^{c} \frac{p_i-1}{p_i}\) の最大値を抑えればよいです。

メルテンスの定理を用いると、\(\prod_{p \le n} \frac{p-1}{p}= \frac{e^{-\gamma} + \mathrm{o}(1)}{\log n}\) で抑えられます。この値は \(N = 500\) で \(0.089\) 程度になります。また、 \(2,3,\dots,59\) を入れると総和が \(440\) となり、\(13.3 \%\) 程で成功します。

実際に \(C = 50\) とすると今回のジャッジにて AC を取ることが出来ます。