Let \(G = \{1,2,\ldots, P-1\}\). Below, multiplication, division, exponentiations, and so on are all performed modulo \(P\). Also, since the problem asks about a Hamiltonian cycle in an undirected graph where \(G\) is the vertex set and edges are spun between two vertices when one is the other multiplied by \(a\) or \(b\), we frequently use the terms in graph theory.

Let the subset \(G_{a,b}\) of \(G\) be defined by \(G_{a,b} = \{a^ib^j\mid i, j\in \mathbb{Z}\}\) (\(\mathbb{Z}\) is the set of all integers). To build a hamiltonian path, every vertex should be reachable from \(1\), so \(G = G_{a,b}\) must hold. Let us examine the structure of \(G_{a,b}\) first.

---

◆The structure of \(G_{a,b}\)

Let us take the minimum \(n\geq 1\) such that \(a^n = 1\) and let \(H = \{a^i\mid 0 \leq i < n\}\). Since \(a^n = 1\), we can also represent it as \(H = \{a^i\mid i\in \mathbb{Z}\}\). Also, let us take the minimum \(m\geq 1\) such that \(b^m\in H\). Then, the following holds:

• For every \(x\in G_{a,b}\), there uniquely exist integers \(0\leq i < n\) and \(0\leq j < m\) such that \(x = a^ib^j\).

【Proof】

(Existence) Let us arbitrarily take an element \(x = a^kb^l\) (\(k, l\in \mathbb{Z}\)) of \(G_{a,b}\). If we let \(q\) and \(j\) be the quotient and remainder when \(l\) is divided by \(m\), it follows from \(l = qm + j\) that \(a^kb^l = a^k(b^m)^qb^j\). From \(b^m\in H\), we have \(a^k(b^m)^q \in H\), so there exists some \(0\leq i < n\) such that \(a^k(b^m)^q = a^i\). Therefore, \(x = a^kb^l = a^ib^j\), and these \(i\) and \(j\) satisfy \(0\leq i < n\) and \(0\leq j < m\), so we have shown the existence of them.

(Uniqueness) Let us assume for \(0\leq i_1, i_2 < n\) and \(0\leq j_1, j_2 < m\) that \(a^{i_1}b^{j_1} = a^{i_2}b^{j_2}\). Proving \(i_1 = i_2\) and \(j_1 = j_2\) will prove the uniqueness of them. Without loss of generality, we assume \(j_1 \leq j_2\). It follows from \(a^{i_1}b^{j_1} = a^{i_2}b^{j_2}\) that \(a^{i_1-i_2} = b^{j_2-j_1}\). Particularly, we have \(b^{j_2-j_1}\in H\). Since \(0\leq j_2-j_1 < m\), we can see from the way we chose \(m\) (the part “let us take the minimum \(m\geq 1\)”) that \(j_2 - j_1 = 0\), that is, \(j_1 = j_2\). Therefore, \(a^{i_1} = a^{i_2}\). Similarly, using \(a^{i_1 - i_2} = 1\) and the definition of \(n\) and so on, we can see that \(i_1 = i_2\). Therefore, it is shown that \(i_1 = i_2\) and \(j_1 = j_2\).

---

◆The necessary condition

Based on the above groundwork, we can obtain the necessary condition for the existence of the hamiltonian cycle in question. It is necessary that \(G=G_{a,b}\), which will be \(|G_{a,b}| = nm\) after taking \(n\) and \(m\) as stated above, so it is necessary that \(P - 1 = nm\).

Below, we assume that this necessary condition is satisfied.

---

◆The connection between \(G\) and a grid graph

Remember that every element in \(G = G_{a,b}\) is uniquely written in the form \(a^ib^j\) (\(0\leq i < n\), \(0\leq j < m\)). From this, by associating a n element of \(G\) with a square \((i, j)\), we can see that \(G\) contains an \(n \times m\) grid graph as a subgraph. That is, if we put \(a^ib^j\) at the \(i\)-th row and \(j\)-th column, adjacent squares will contain numbers connected by an edge in the problem.

For example, the figure below shows the placements of numbers for the case \(P = 13\), \(a = 4\), and \(b = 5\).

Actually, there are also edges “outside” the grid. In the above example, we can go between positions where the same English letter is written in the figure to the right. From \(a^n = 1\), for the direction of moves regarding multiplying by \(a\), we can go between the top and bottom rows in the same column.

---

◆Building a Hamiltonian Cycle

If \(n = 1\) or \(m = 1\):

In this case, the \(n\times m\) grid graph may not contain a Hamiltonian cycle, but we can build one by using the edge outside the grid. One such example is 【Sample Input 2】.

If \(n, m > 1\) (Method 1)

In this case, it follows from \(P > 2\) that \(nm = P - 1\) is even, so \(n\) or \(m\) is even. If \(m\) is even, we can build a Hamiltonian cycle in the following form:

If \(m\) is odd, rotate the grid and build a similar cycle.

If \(n, m > 1\) (Method 2)

It was not in the writer’s mind that \(nm\) was even. By using the move between the top and bottom rows in the same column, we can build a Hamiltonian cycle as follows:

If \(n, m > 1\) (Method 3 by Tester)

If \(n\) is odd under the necessary condition, we can prove that swapping \(a, b\) and recalculate \(n, m\) makes \(n\) even. From the facts that \(n\) is even and that we can go between the top and bottom rows in the same column, we can build the following Hamiltonian cycle: