Swap to Rearrange

Treat every index as an edge. This is the whole problem; the arrays are just wearing a fake mustache.

For every position $i$, we have two values $a_i$ and $b_i$. After all operations, exactly one of them is in the top array and the other is in the bottom array. So if we draw an edge between vertices $a_i$ and $b_i$, then choosing the final state of index $i$ is choosing an orientation of that edge:

• edge oriented $a_i \to b_i$: do not swap index $i$;
• edge oriented $b_i \to a_i$: swap index $i$.

Now look at one value $x$. In the final arrays:

• the number of times $x$ appears in $a$ is the number of edges oriented out of $x$;
• the number of times $x$ appears in $b$ is the number of edges oriented into $x$.

Edges with $a_i=b_i=x$ contribute one $x$ to both arrays no matter what, so they are irrelevant. We can ignore loops completely.

Therefore the task becomes:

Can we orient every non-loop edge of an undirected multigraph so that for every vertex $x$, $\operatorname{out}(x)=\operatorname{in}(x)$?

That means every vertex must have even degree. If $\deg(x)$ is odd, then $\operatorname{out}(x)+\operatorname{in}(x)=\deg(x)$ is odd, so the two counts cannot be equal. Impossible.

If every degree is even, each connected component is Eulerian. Take an Euler cycle in each component and orient every traversed edge in the direction it is walked. At every vertex, every time the tour enters it, it also leaves it. Since the tour is closed, this pairs all incident edges into one incoming and one outgoing edge. So every vertex becomes balanced.

That proves the condition is both necessary and sufficient:

$$\text{answer exists} \iff \forall x,\ \deg(x) \text{ is even}.$$

Implementation details:

1. Ignore all indices where $a_i=b_i$.
2. For every other index $i$, add an undirected edge between $a_i$ and $b_i$ and increase both degrees.
3. If any degree is odd, print $-1$.
4. Otherwise, run iterative Hierholzer DFS over the multigraph.
5. When traversing an unused edge from vertex $u$ to vertex $v$, we orient it as $u \to v$.
6. If the original edge was $a_i \to b_i$ and our orientation is $b_i \to a_i$, then index $i$ must be swapped.

Parallel edges are fine. Disconnected components are fine. Loops were ignored because they are already balanced. No minimization is needed, so this Euler orientation is enough.

Complexity is linear:

$$O(n)$$

per total input size across all test cases, with $O(n)$ memory. Fits easily inside the limits; no dark magic, just graph parity doing the heavy lifting.