Let \(G\) be a graph with \(NK\) vertices, where there are \(NK\) edges \((i, P_i)\).

To sort \(P\) in ascending order with the minimum number of operations, we can repeatedly choose vertices \(i, j (i \neq j)\) in \(G\) that belong to the same connected component and swap \(P_i\) and \(P_j\).

From this, we know that we can find the answer for each connected component and output their sum. Hereafter, let’s choose one connected component of \(G\), assume its size is \(n\), and consider the answer for that connected component.

Choose and define a sequence \(Q = (Q_1, Q_2, \ldots, Q_n)\) that satisfies all of the following conditions:

• All elements contained in \(Q\) are vertex numbers of the chosen connected component.
• \(Q_{i+1} = P_{Q_i}\)
• \(Q_1 = P_{Q_n}\)

When we define \(f(Q)\) as the answer to the following problem using this \(Q\), \(f(Q)\) becomes the same as the answer to the original problem (for the reason described later).

A good tree is a tree with \(n\) vertices where, when vertices \(1, 2, \ldots, n\) are arranged on a circle, the edges do not intersect.

The score of a tree is the number of integers \(a < b\) such that \((a, b) \in E\) and \(Q_a \equiv Q_b \pmod{N}\).

Find the maximum score among all good trees.

The edges correspond to pairs of indices to swap.

\(f(Q)\) can be computed in \(\Theta(n^3)\) time complexity using simple interval DP. Specifically, define \(\mathrm{dp}[l][r]\) as the maximum number of edges that can be adopted such that \(l \leq i < j < r\) and \(Q_i \equiv Q_j \pmod{N}\), and update appropriately.

Here, for the condition of good trees in the problem of finding \(f(Q)\), even if we add the following condition, \(f(Q)\) does not change:

• There do not exist \(a, b, c\) such that \((a, b) \in E\), \((a, c) \in E\), \(Q_a \equiv Q_b \equiv Q_c \pmod{N}\), and \(a < b < c\).

This is because if such \(a, b, c\) exist, removing edge \((a, c)\) and adding edge \((b, c)\) does not change the score.

Therefore, we can limit the updates of interval DP as follows:

• \(\mathrm{dp}[l][r] \leftarrow \mathrm{dp}[l+1][r]\)
• \(\mathrm{dp}[l][r] \leftarrow \mathrm{dp}[l+1][k] + \mathrm{dp}[k][r] + 1\) (only when \(Q_l \equiv Q_k\))

The above updates occur \(\Theta(n^2)\) times for the first type and \(\Theta(n^2 K)\) times for the second type, so the computational complexity per connected component becomes \(\Theta(n^2 K)\).

The overall computational complexity becomes \(\Theta(N^2 K^3)\), which is sufficiently fast under the constraints of this problem.

Implementation Examples

C++ Implementation Example

PyPy Implementation Example

---

Reason for Reduction to Another Problem

For simplicity, assume \(n \neq 1\).

Among the \(n-1\) swaps, if we perform a swap of \(P_i, P_j\), then using integers \(a, b\) that satisfy \(Q_a = i, Q_b = j\), we draw an edge connecting vertices \(a, b\).

From Swaps to Trees

In this case, we cannot draw edges in a way that they intersect. This is because such \(i, j\) already exist in different connected components on \(G\), and swapping such two indices is not an operation suitable for sorting \(P\) in ascending order with the minimum number of operations.

Also, there must be no cycles. The operation of swapping \(i, j\) corresponds to decomposing vertices \(i, j\) into different connected components on \(G\), so when adding an edge creates a cycle, they already belong to different connected components.

Therefore, when we correspond swap operations to edge-drawing operations on vertices in the problem of finding \(f(Q)\), we get a tree where edges do not intersect.

From Trees to Swaps

For any edge set \(E\) of a good tree, there always exists an \(i\) such that \((i, i+1) \in E\) and either vertex \(i\) or vertex \((i+1)\) is a leaf.

If we assume this doesn’t exist, then taking a leaf \(a\) and a vertex \(b\) directly connected to vertex \(a\) such that \(|a-b|\) is minimum, there would be no leaf in \(a < c < b\), but it can be shown that such a tree cannot exist.

Choose one \(i\) such that \((i, i+1) \in E\) and either vertex \(i\) or vertex \((i+1)\) is a leaf. If vertex \(i+1\) is a leaf, we decide to perform the swap \((i, i+1)\) first; otherwise, we perform the swap \((i, i+1)\) last, reducing to a case where \(n\) is smaller by one. By doing this, we can show that a valid sequence of swap operations can be constructed from the tree.