← 返回题目列表

Codeforces · 1783/F

F. 双重排序II

中文机器翻译题面 查看原题

给你两个排列 $$$a$$$ 和 $$$b$$$,大小都是 $$$n$$$。大小为 $$$n$$$ 的排列是 $$$n$$$ 元素的数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次。每个排列中的元素索引从 $$$1$$$ 到 $$$n$$$。

您可以多次执行以下操作:

- 从 $$$1$$$ 到 $$$n$$$ 中选择一个整数 $$$i$$$;
- 令 $$$x$$$ 为整数,使得 $$$a_x = i$$$。将 $$$a_i$$$ 与 $$$a_x$$$ 交换;
- 令 $$$y$$$ 为整数,使得 $$$b_y = i$$$。将 $$$b_i$$$ 与 $$$b_y$$$ 交换。

您的目标是使用最少的操作数使两个排列按升序排序(即必须满足条件 $$$a_1 < a_2 < \dots < a_n$$$ 和 $$$b_1 < b_2 < \dots < b_n$$$)。请注意,在执行您选择的操作序列后,必须对两种排列进行排序。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3000$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$;所有 $$$a_i$$$ 都是不同的)。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$;所有 $$$b_i$$$ 都是不同的)。

输出

首先,打印一个整数 $$$k$$$ ($$$0 \le k \le 2n$$$) — 对两种排列进行排序所需的最少操作数。请注意,可以证明 $$$2n$$$ 操作总是足够的。

然后,打印 $$$k$$$ 整数 $$$op_1, op_2, \dots, op_k$$$ ($$$1 \le op_j \le n$$$),其中 $$$op_j$$$ 是您在第 $$$j$$$ 操作期间选择的 $$$i$$$ 的值。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

5
1 3 2 4 5
2 1 3 4 5

输出 #1

1
2

输入 #2

2
1 2
1 2

输出 #2

0

输入 #3

4
1 3 4 2
4 3 2 1

输出 #3

2
3 4