H. Peak Productivity Forces
constructive algorithms
I'm peakly productive and this is deep.You are given two permutations\(^{\text{∗}}\) \(a\) and \(b\), both of length \(n\).You can perform the following three-step operation on permutation \(a\): Choose an index \(i\) (\(1 \le i \le n\)). Cyclic shift \(a_1, a_2, \ldots, a_{i-1}\) by \(1\) to the right. If you had chosen \(i = 1\), then this range doesn't exist, and you cyclic shift nothing. Cyclic shift \(a_{i + 1}, a_{i + 2}, \ldots, a_n\) by \(1\) to the right. If you had chosen \(i = n\), then this range doesn't exist, and you cyclic shift nothing.After the operation, \(a_1,a_2,\ldots, a_{i-2},a_{i-1},a_i,a_{i + 1}, a_{i + 2},\ldots,a_{n-1}, a_n\) is transformed into \(a_{i-1},a_1,\ldots,a_{i-3},a_{i-2},a_i,a_n, a_{i + 1},\ldots,a_{n-2}, a_{n-1}\).Here are some examples of operations done on the identity permutation \([1,2,3,4,5,6,7]\) of length \(7\): If we choose \(i = 3\), it will become \([2, 1, 3, 7, 4, 5, 6]\). If we choose \(i = 1\), it will become \([1, 7, 2, 3, 4, 5, 6]\). If we choose \(i = 7\), it will become \([6, 1, 2, 3, 4, 5, 7]\). Notably, position \(i\) is not shifted. Find a construction using at most \(2n\) operations to make \(a\) equal to \(b\) or print \(-1\) if it is impossible. The number of operations does not need to be minimized. It can be shown that if it is possible to make \(a\) equal to \(b\), it is possible to do this within \(2n\) operations. \(^{\text{∗}}\)A permutation of length \(n\) is an array consisting of \(n\) distinct integers from \(1\) to \(n\) in arbitrary order. For example, \([2,3,1,5,4]\) is a permutation, but \([1,2,2]\) is not a permutation (\(2\) appears twice in the array), and \([1,3,4]\) is also not a permutation (\(n=3\) but there is \(4\) in the array).
The first line contains a single integer \(t\) (\(1 \le t \le 5 \cdot 10^4\)) — the number of test cases.The first line of each test case contains a single integer \(n\) (\(1 \le n \le 5 \cdot 10^5\)) — the lengths of permutations \(a\) and \(b\).The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)) — the values of permutation \(a\).The third line of each test case contains \(n\) integers \(b_1, b_2, \ldots, b_n\) (\(1 \le b_i \le n\)) — the values of permutation \(b\).It is guaranteed that the sum of \(n\) over all test cases will not exceed \(5 \cdot 10^5\).
For each test case:If there is a sequence of operations to transform \(a\) into \(b\), output a single integer \(q\) (\(0\le q\le 2n\)) — the number of operations in the first line and \(q\) integers with the \(i\)-th number representing the index of the \(i\)-th operation in the second line.If there is no sequence of operations, output \(-1\) in the only line.
In the first case, you can do no operation since \(a=b\).In the second case, it can be proved \(a\) can not be transformed into \(b\).In the third case, \(a\) is transformed into \([2,3,1]\) after the first operation and into \(b\) after the second operation.