← Home
write a go solution for Description:
You are given two permutations a and b, both of size n. A permutation of size n is an array of n elements, where each integer from 1 to n appears exactly once. The elements in each permutation are indexed from 1 to n.

You can perform the following operation any number of times:

- choose an integer i from 1 to n;
- let x be the integer such that a_x=i. Swap a_i with a_x;
- let y be the integer such that b_y=i. Swap b_i with b_y.

Your goal is to make both permutations sorted in ascending order (i. e. the conditions a_1<a_2<...<a_n and b_1<b_2<...<b_n must be satisfied) using minimum number of operations. Note that both permutations must be sorted after you perform the sequence of operations you have chosen.

Input Format:
The first line contains one integer n (2<=n<=3000).

The second line contains n integers a_1,a_2,...,a_n (1<=a_i<=n; all a_i are distinct).

The third line contains n integers b_1,b_2,...,b_n (1<=b_i<=n; all b_i are distinct).

Output Format:
First, print one integer k (0<=k<=2n) — the minimum number of operations required to sort both permutations. Note that it can be shown that 2n operations are always enough.

Then, print k integers op_1,op_2,...,op_k (1<=op_j<=n), where op_j is the value of i you choose during the j-th operation.

If there are multiple answers, print any of them.

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