When \((x, y) \in S\), we also include \((y, x) \in S\), and simply allow operations when \((P_l, P_r) \in S\).

Here, we observe that if \((x, y) \in S\) and \((y, z) \in S\), then adding \((x, z)\) to \(S\) does not change the problem.

Thus, \(S\) can be viewed as the edge set of an undirected graph, and we can think of performing operations on pairs of vertices \((x, y)\) that are connected.

We can then adopt the following strategy:

• First, determine the sequence of connected components using reverse operations. Then, using swap operations, greedily assign the smallest available vertex in each connected component from left to right.

We consider what sequences of connected components are achievable via reverse operations. Consider the following problem:

• We have an integer sequence \(X\) of length \(N\). We can do this operation any number of times: choose \((l, r)\) such that \(X_l = X_r\) and reverse \(X_l, \ldots, X_r\). What sequences \(X\) can be produced?

The necessary and sufficient condition for a sequence \(Y\) to be producible is as follows. (Proof given later.)

• Construct an undirected graph \(G\): for \(i = 1, 2, \ldots, N-1\), add an edge between vertices \(X_i\) and \(X_{i+1}\). Then,
  • \(Y_1 = X_1\)
  • \(Y\) is the sequence of vertex numbers of an Eulerian path in \(G\).

Returning to the original problem. First, we prepare a graph \(G_1\) with \(N\) vertices and add an edge between vertices \(x\) and \(y\) for each \((x, y)\). Let \(K\) be the number of connected components in \(G_1\), and number them from \(1\) to \(K\). Next, we prepare a graph \(G_2\) with \(K\) vertices. For \(i = 1, 2, \ldots, N-1\), let \(a\) and \(b\) be the component numbers of \(P_i\) and \(P_{i+1}\) in \(G_1\), respectively, and add an edge between vertices \(a\) and \(b\) in \(G_2\).

We can obtain the answer permutation \(\mathrm{ans}\) by constructing an Eulerian path on \(G_2\) as follows:

• Let \(g\) be the component number of \(P_1\) in \(G_1\).
• Repeat the following \(N\) times:
  • Append to \(\mathrm{ans}\) the vertex numbers in component \(g\) of \(G_1\) that have not yet been added.
  • Among the vertices adjacent to \(g\) in \(G_2\), let \(g'\) be one satisfying:
    • Proceeding to \(g'\) next still allows an Eulerian path in \(G_2\) to be constructed.
    • If multiple such vertices exist, let \(g'\) be the component number containing the smallest vertex number not yet in \(\mathrm{ans}\).
  • Set \(g = g'\).

A naive implementation of this is \(O(N^2)\), but by using sqrt decomposition on component sizes, it becomes \(O(N^{1.5})\). An \(O(N^{1.5} \log N)\) solution should also pass if the constant factor is not too large.

---

A sqrt decomposition strategy that is easy to implement

Manage the adjacency list of \(G_2\) using an associative array. For each connected component, maintain the ability to retrieve the remaining minimum vertex in \(O(1)\).

• Small connected components: look at all adjacent vertices in \(G_2\) and retrieve the component with the smallest vertex in \(O(\sqrt{N})\).
• Large connected components: for each connected component, maintain a counter \(\mathrm{now} = 1\). Repeat the following:
  • If vertex \(\mathrm{now}\) has not been used and there is a remaining edge in \(G_2\) between the vertex corresponding to the current component and the vertex corresponding to the component containing \(\mathrm{now}\), then \(\mathrm{now}\) is the next vertex to proceed to.
  • Otherwise, increment \(\mathrm{now}\) and return to the above.
  • For a single large connected component, all these operations take \(O(N)\) in total.

Once the next vertex to proceed to is determined, delete the edge between the two corresponding vertices in the associative array managing \(G_2\)’s adjacency list.

---

Proof of Necessity and Sufficiency

Necessity

The graph obtained from \(X\) is invariant under reverse operations. Thus, the shape of the graph is an invariant, and the graph obtained from \(Y\) must be the same as the one obtained from \(X\).

Sufficiency

We prove this by induction. Assume \(X_1 = Y_1\) and \(X_2 \neq Y_2\). Our goal is to make \(X_2 = Y_2\). Since \(X\) and \(Y\) correspond to Eulerian paths of the same graph, there exists an \(i\) such that \((Y_1, Y_2) = (X_{i+1}, X_i)\) or \((Y_1, Y_2) = (X_i, X_{i+1})\).

1. When there exists \(i\) such that \((Y_1, Y_2) = (X_{i+1}, X_i)\):
   Applying the operation with \((l, r) = (1, i+1)\) to \(X\) gives \(X_1 = Y_1\) and \(X_2 = Y_2\).

2. When there exists \(i\) such that \((Y_1, Y_2) = (X_i, X_{i+1})\):
   There necessarily exists \(L < i+1 \leq R\) with \(X_L = X_R\). Applying the reverse operation to such \(L\) and \(R\) reduces this to case 1.

---

Implementation example (Python)

from atcoder.dsu import DSU
from collections import defaultdict
import sys
sys.setrecursionlimit(3 * 10**5)



def solve():
    n, m = map(int, input().split())
    p = list(map(lambda x: int(x) - 1, input().split()))
    uf = DSU(n)
    for i in range(m):
        x, y = map(lambda x: int(x) - 1, input().split())
        uf.merge(x, y)

    group = [uf.leader(i) for i in range(n)]
    rem = [[] for i in range(n)]
    G2 = [defaultdict(int) for i in range(n)]
    for i in range(n - 1, -1, -1):
        rem[group[i]].append(i)
        if i != 0:
            x, y = group[p[i - 1]], group[p[i]]
            G2[x][y] += 1
            G2[y][x] += 1

    use = [0] * n
    now = [0] * n
    trail = []
    
    def find(g):
        if len(G2[g]) < 300:
            mn = n
            for u, c in G2[g].items():
                if c > 0:
                    mn = min(mn, rem[u][-1])
            return mn
        while now[g] != n:
            g2 = group[now[g]]
            if use[now[g]] == 0 and g2 in G2[g] and G2[g][g2] > 0:
                return now[g]
            now[g] += 1
        return n

    def Eulerian(g):
        tmp = rem[g].pop()
        use[tmp] = 1
        while True:
            nxt = find(g)
            if nxt == n:
                break
            ng = group[nxt]
            G2[g][ng] -= 1
            G2[ng][g] -= 1
            Eulerian(ng)
        trail.append(tmp)

    Eulerian(group[p[0]])
    print(*[i + 1 for i in trail[::-1]])


for _ in range(int(input())):
    solve()