Columns Swaps (Codeforces 1385G)
Tags: Implement, 2-sat

You are given a table $$$a$$$ of size $$$2 \times n$$$ (i.e. two rows and $$$n$$$ columns) consisting of integers from $$$1$$$ to $$$n$$$.In one move, you can choose some column $$$j$$$ ($$$1 \le j \le n$$$) and swap values $$$a_{1, j}$$$ and $$$a_{2, j}$$$ in it. Each column can be chosen no more than once.Your task is to find the minimum number of moves required to obtain permutations of size $$$n$$$ in both first and second rows of the table or determine if it is impossible to do that.You have to answer $$$t$$$ independent test cases.Recall that the permutation of size $$$n$$$ is such an array of size $$$n$$$ that contains each integer from $$$1$$$ to $$$n$$$ exactly once (the order of elements doesn't matter).

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.The first line of the test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of columns in the table. The second line of the test case contains $$$n$$$ integers $$$a_{1, 1}, a_{1, 2}, \dots, a_{1, n}$$$ ($$$1 \le a_{1, i} \le n$$$), where $$$a_{1, i}$$$ is the $$$i$$$-th element of the first row of the table. The third line of the test case contains $$$n$$$ integers $$$a_{2, 1}, a_{2, 2}, \dots, a_{2, n}$$$ ($$$1 \le a_{2, i} \le n$$$), where $$$a_{2, i}$$$ is the $$$i$$$-th element of the second row of the table.It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output: For each test case print the answer: -1 if it is impossible to obtain permutation of size $$$n$$$ in both first and the second rows of the table, or one integer $$$k$$$ in the first line, where $$$k$$$ is the minimum number of moves required to obtain permutations in both rows, and $$$k$$$ distinct integers $$$pos_1, pos_2, \dots, pos_k$$$ in the second line ($$$1 \le pos_i \le n$$$) in any order — indices of columns in which you need to swap values to obtain permutations in both rows. If there are several answers, you can print any.


Sample Inputs:
6
4
1 2 3 4
2 3 1 4
5
5 3 5 1 4
1 2 3 2 4
3
1 2 1
3 3 2
4
1 2 2 1
3 4 3 4
4
4 3 1 4
3 2 2 1
3
1 1 2
3 2 2

Sample Outputs:
0

2
2 3 
1
1 
2
3 4 
2
3 4 
-1

Solution (Python):
import sys

def input():
    return sys.stdin.readline().strip()

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    pos = [[] for i in range(n + 1)]
    for i in range(n):
        pos[a[i]].extend((i, 0))
        pos[b[i]].extend((i, 1))
        if len(pos[a[i]]) > 4 or len(pos[b[i]]) > 4:
            print(-1)
            return
    was = [False] * (n + 1)
    res = []
    for i in range(1, n):
        if not was[i]:
            x = i
            p = pos[i][0]
            if pos[i][1] == 1:
                (one, two) = ([p], [])
            else:
                (one, two) = ([], [p])
            first = p
            while True:
                was[x] = True
                if pos[x][0] == p:
                    p = pos[x][2]
                    if p == first:
                        break
                    r = pos[x][3]
                else:
                    p = pos[x][0]
                    if p == first:
                        break
                    r = pos[x][1]
                if r == 0:
                    one.append(p)
                    x = b[p]
                else:
                    two.append(p)
                    x = a[p]
            if len(one) > len(two):
                one = two
            res.extend(one)
    ''
    print(len(res))
    print(' '.join([str(i + 1) for i in res]))
for i in range(int(input())):
    solve()

Solution (Python):
t = int(input())
Maxn = 210000
while t > 0:
    t -= 1
    n = int(input())
    a = input().split()
    b = input().split()
    a1 = [-1] * (n + 1)
    a2 = [-1] * (n + 1)
    b1 = [-1] * (n + 1)
    b2 = [-1] * (n + 1)
    for i in range(0, n):
        now = int(a[i])
        if a1[now] == -1:
            a1[now] = i
            b1[now] = 1
        else:
            a2[now] = i
            b2[now] = 1
        now = int(b[i])
        if a1[now] == -1:
            a1[now] = i
            b1[now] = 2
        else:
            a2[now] = i
            b2[now] = 2
    flag = 0
    for i in range(1, n + 1):
        if a2[i] == -1:
            print('-1')
            flag = 1
            break
    if flag:
        continue
    to = []
    nxt = []
    w = []
    que = []
    first = [-1] * (n + 1)
    col = [-1] * (n + 1)

    def add(u, v, wi):
        to.append(v)
        nxt.append(first[u])
        w.append(wi)
        first[u] = len(to) - 1
        to.append(u)
        nxt.append(first[v])
        first[v] = len(to) - 1
        w.append(wi)
    for i in range(1, n + 1):
        if a1[i] == a2[i]:
            continue
        elif b1[i] == b2[i]:
            add(a1[i], a2[i], 1)
        else:
            add(a1[i], a2[i], 0)
    ans = []
    for i in range(0, n):
        if first[i] != -1 and col[i] == -1:
            col[i] = 0
            que.append(i)
            q = [[i], []]
            while len(que):
                now = que.pop()
                cur = first[now]
                while cur != -1:
                    if col[to[cur]] == -1:
                        if w[cur] == 0:
                            col[to[cur]] = col[now]
                        else:
                            col[to[cur]] = (col[now] + 1) % 2
                        q[col[to[cur]]].append(to[cur])
                        que.append(to[cur])
                    cur = nxt[cur]
            if len(q[0]) < len(q[1]):
                while len(q[0]):
                    ans.append(q[0].pop() + 1)
            else:
                while len(q[1]):
                    ans.append(q[1].pop() + 1)
    print(len(ans))
    for i in ans:
        print(i, end=' ')
    print('')

Solution (Python):
import sys
inp = [int(x) for x in sys.stdin.read().split()]
ii = 0
out = []

def solve(n, A):
    same = [-1] * (2 * n)
    pos = [-1] * n
    for i in range(2 * n):
        a = A[i]
        if pos[a] == -1:
            pos[a] = i
        elif pos[a] == -2:
            return None
        else:
            p = pos[a]
            pos[a] = -2
            same[p] = i
            same[i] = p
    ans = []
    found = [0] * (2 * n)
    for root in range(2 * n):
        if found[root]:
            continue
        count0 = []
        count1 = []
        node = root
        while not found[node]:
            found[node] = 1
            found[same[node]] = 1
            if node & 1:
                count0.append(node >> 1)
            else:
                count1.append(node >> 1)
            node = same[node ^ 1]
        if len(count0) < len(count1):
            ans += count0
        else:
            ans += count1
    return ans
t = inp[ii]
ii += 1
for _ in range(t):
    n = inp[ii]
    ii += 1
    A = [x - 1 for x in inp[ii:ii + n]]
    ii += n
    B = [x - 1 for x in inp[ii:ii + n]]
    ii += n
    A = [A[i >> 1] if i & 1 == 0 else B[i >> 1] for i in range(2 * n)]
    ans = solve(n, A)
    if ans is None:
        out.append('-1')
    else:
        out.append(str(len(ans)))
        out.append(' '.join((str(x + 1) for x in ans)))
print('\n'.join(out))