← Home
write a go solution for Description:
You are given a table a of size 2xn (i.e. two rows and n columns) consisting of integers from 1 to n.

In one move, you can choose some column j (1<=j<=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 Format:
The first line of the input contains one integer t (1<=t<=2*10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains one integer n (1<=n<=2*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,...,a_1,n (1<=a_1,i<=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,...,a_2,n (1<=a_2,i<=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*10^5 (sumn<=2*10^5).

Output Format:
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,...,pos_k in the second line (1<=pos_i<=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.

Note:
None. Output only the code with no comments, explanation, or additional text.