\(G = \{1,2,\ldots, P-1\}\) とし、以下、積・商・べき乗などはすべて \(\pmod{P}\) での計算を表すものとします。この問題では、\(G\) を頂点集合とし、「\(a\) 倍または \(b\) 倍」という関係で辺を張った無向グラフにおけるハミルトン閉路について問うています。解説でもしばしばグラフの用語を用います。

\(G\) の部分集合 \(G_{a,b}\) を、\(G_{a,b} = \{a^ib^j\mid i, j\in \mathbb{Z}\}\) により定めることにします（\(\mathbb{Z}\) は整数全体の集合）。ハミルトン閉路を構築するためには、\(1\) から任意の点に到達可能でなければいけません。したがって、\(G = G_{a,b}\) が成り立つ必要があります。まずは \(G_{a,b}\) の構造を調べましょう。

---

◆\(G_{a,b}\) の構造

\(a^n = 1\) となる最小の \(n\geq 1\) をとり、\(H = \{a^i\mid 0 \leq i < n\}\) とします。\(a^n = 1\) より、\(H = \{a^i\mid i\in \mathbb{Z}\}\) と表すこともできます。 また、\(b^m\in H\) となる最小の \(m\geq 1\) をとります。このとき次が成り立ちます：

• 任意の \(x\in G_{a,b}\) に対して、整数 \(0\leq i < n\) および \(0\leq j < m\) であって、\(x = a^ib^j\) となるものが一意に存在する。

【証明】

（存在） \(G_{a,b}\) の元 \(x = a^kb^l\) (\(k, l\in \mathbb{Z}\)) を任意にとる。\(l\) を \(m\) で割った商・余りを \(q, j\) とすれば、\(l = qm + j\) より \(a^kb^l = a^k(b^m)^qb^j\) が成り立つ。\(b^m\in H\) より \(a^k(b^m)^q \in H\) なので、ある \(0\leq i < n\) が存在して \(a^k(b^m)^q = a^i\) である。したがって \(x = a^kb^l = a^ib^j\) であり、この \(i,j\) は \(0\leq i < n\), \(0\leq j < m\) を満たすので存在が示された。

（一意性） \(0\leq i_1, i_2 < n\), \(0\leq j_1, j_2 < m\) に対して \(a^{i_1}b^{j_1} = a^{i_2}b^{j_2}\) が成り立つと仮定する。\(i_1 = i_2\) かつ \(j_1 = j_2\) であることを示せばよい。\(j_1 \leq j_2\) としても一般性を失わない。 \(a^{i_1}b^{j_1} = a^{i_2}b^{j_2}\) より \(a^{i_1-i_2} = b^{j_2-j_1}\) である。特に \(b^{j_2-j_1}\in H\) となる。\(0\leq j_2-j_1 < m\) であるから、\(m\) のとり方（「\(1\) 以上で最小のもの」という部分）から \(j_2 - j_1 = 0\) つまり \(j_1 = j_2\) であることが分かる。したがって、\(a^{i_1} = a^{i_2}\) である。\(a^{i_1 - i_2} = 1\) と \(n\) の定義などを用いると、\(i_1 = i_2\) であることも同様に分かる。よって \(i_1 = i_2\) かつ \(j_1 = j_2\) が示された。

---

◆必要条件

以上の準備を元に、問題のハミルトン閉路が存在するための必要条件が得られます。\(G=G_{a,b}\) が必要ですが、上述のように \(n, m\) をとれば \(|G_{a,b}| = nm\) となるので、必要条件 \(P - 1 = nm\) が得られます。

以下、この必要条件が満たされているとします。

---

◆\(G\) とグリッドグラフの関係

\(G = G_{a,b}\) の任意の元は \(a^ib^j\) (\(0\leq i < n\), \(0\leq j < m\)) の形に一意に表されるのでした。これにより、\(G\) の元をマス \((i,j)\) に対応させることで、\(G\) は \(n\times m\) のグリッドグラフを部分グラフとして含むことが分かります。つまり、\(i\) 行 \(j\) 列目に \(a^ib^j\) を配置した場合、隣接するマス目には、本問において辺が張られている \(2\) 数が配置されます。

例えば次の図は、\(P = 13\), \(a = 4\), \(b = 5\) とした場合の配置を図示しています。

実際には隣接したマス目の間だけではなく、「マス目の外側に向かう方向」にも辺があり、上の例では右図において同じアルファベットを書き込んである部分同士が行き来可能です。\(a^n = 1\) より、 \(a\) 倍方向の移動については同じ列の最上段と最下段が行き来可能です。

---

◆ハミルトン閉路の構築

\(n = 1\) または \(m = 1\) のとき

\(n = 1\) または \(m = 1\) のときは、\(n\times m\) のグリッドグラフにおいてはハミルトン閉路が存在するとは限りませんが、マス目の外に向かう辺に沿って進むことで、ハミルトン閉路が構築できます。例えば 【入力例 2】 がそのような場合となっています。

\(n, m > 1\) のとき（方法 1）

このとき \(P > 2\) より \(nm = P - 1\) は偶数なので、\(n\) または \(m\) は偶数です。例えば \(m\) が偶数だとすると、次の形の ハミルトン閉路が構築できます。

\(m\) が奇数ならば、縦・横を入れ替えて同様の構築をすればよいです。

\(n, m > 1\) のとき（方法 2）

writer ははじめ、\(nm\) が偶数であることを意識していませんでした。その場合でも、同じ列の最上段と最下段が行き来可能であることに注意すると、次のように ハミルトン閉路を構築できます。

\(n, m > 1\) のとき（方法 3, tester 解）

必要条件のもと、\(n\) が奇数になるならば、\(a, b\) を入れ替えて \(n, m\) を計算しなおすと今度は \(n\) が偶数になることが証明できます。\(n\) が偶数であることと、同じ列の最上段と最下段が行き来可能であることから、次のようなハミルトン閉路が構築できます。