#P1783F. Double Sort II

    ID: 8099 Type: RemoteJudge 2000ms 512MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>constructive algorithmsdfs and similarflowsgraph matchingsgraphsgreedy

Double Sort II

No submission language available for this problem.

Description

You are given two permutations aa and bb, both of size nn. A permutation of size nn is an array of nn elements, where each integer from 11 to nn appears exactly once. The elements in each permutation are indexed from 11 to nn.

You can perform the following operation any number of times:

  • choose an integer ii from 11 to nn;
  • let xx be the integer such that ax=ia_x = i. Swap aia_i with axa_x;
  • let yy be the integer such that by=ib_y = i. Swap bib_i with byb_y.

Your goal is to make both permutations sorted in ascending order (i. e. the conditions a1<a2<<ana_1 < a_2 < \dots < a_n and b1<b2<<bnb_1 < b_2 < \dots < 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.

The first line contains one integer nn (2n30002 \le n \le 3000).

The second line contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ain1 \le a_i \le n; all aia_i are distinct).

The third line contains nn integers b1,b2,,bnb_1, b_2, \dots, b_n (1bin1 \le b_i \le n; all bib_i are distinct).

First, print one integer kk (0k2n0 \le k \le 2n) — the minimum number of operations required to sort both permutations. Note that it can be shown that 2n2n operations are always enough.

Then, print kk integers op1,op2,,opkop_1, op_2, \dots, op_k (1opjn1 \le op_j \le n), where opjop_j is the value of ii you choose during the jj-th operation.

If there are multiple answers, print any of them.

Input

The first line contains one integer nn (2n30002 \le n \le 3000).

The second line contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ain1 \le a_i \le n; all aia_i are distinct).

The third line contains nn integers b1,b2,,bnb_1, b_2, \dots, b_n (1bin1 \le b_i \le n; all bib_i are distinct).

Output

First, print one integer kk (0k2n0 \le k \le 2n) — the minimum number of operations required to sort both permutations. Note that it can be shown that 2n2n operations are always enough.

Then, print kk integers op1,op2,,opkop_1, op_2, \dots, op_k (1opjn1 \le op_j \le n), where opjop_j is the value of ii you choose during the jj-th operation.

If there are multiple answers, print any of them.

Sample Input 1

5
1 3 2 4 5
2 1 3 4 5

Sample Output 1

1
2

Sample Input 2

2
1 2
1 2

Sample Output 2

0

Sample Input 3

4
1 3 4 2
4 3 2 1

Sample Output 3

2
3 4