Type: Default 1000ms 256MiB

构造的芙莉莲

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

PDF DownLoad

本场竞赛的PDF题面:下载

Problem Description

为什么有些出题人钟爱构造呢?

芙莉莲获得了一本古老的魔法书,书上的符文顺序被打乱了。

书中共有 $n$ 个符文,恰好构成 $1$ 到 $n$ 的一个排列。当前顺序为 $a_1, a_2, \dots, a_n$,正确的激活顺序为 $b_1, b_2, \dots, b_n$。

其中,一个长度为 $n$ 的排列是指长度为 $n$ 的序列,其中 $1,2,\dots n$ 中的每个元素恰好出现一次。

她可以施展以下操作至多 $3n$ 次:

$\quad$· 选择两个不同的页码 $i, j$($1 \le i, j \le n$,$i \neq j$);

$\quad$· 将第 $i$ 页的符文与第 $j$ 页的符文进行融合,使 $a_i$ 变为 $a_i \oplus a_j$,其中 $\oplus$ 表示按位异或。

请判断能否将排列 $a$ 变为目标排列 $b$,若能则给出一个操作序列。

Input Format

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$,保证是 $1$ 到 $n$ 的一个排列。

第三行 $n$ 个整数 $b_1, b_2, \dots, b_n$,保证是 $1$ 到 $n$ 的一个排列。

数据范围保证:

$1\leq n\leq 10^5$,$1\leq a_i,b_i\leq n$。

Output Format

若可以达成目标:

$\quad$ 1. 第一行输出 $\text{‘Yes’}$;

$\quad$ 2. 第二行输出一个整数 $k$($0 \le k \le 3n$),表示操作次数;

$\quad$ 3. 接下来 $k$ 行,每行两个整数 $i, j$($1 \le i, j \le n$,$i \neq j$),依次描述每一步操作。

若无法达成目标,输出一行 $\text{‘No’}$。

注意,你的输出结果不需要带有引号。如果有多种构造方案,你可以选择任意一种,并不需要选择操作次数最少的一种。

3
1 2 3
3 2 1
Yes
2
1 2
3 2

Hint

初始符文排列为 $[1, 2, 3]$,目标排列为 $[3, 2, 1]$。

第一次操作 $i = 1, j = 2$:$a_1$ 变为 $1 \oplus 2 = 3$,排列变为 $[3, 2, 3]$。

第二次操作 $i = 3, j = 2$:$a_3$ 变为 $3 \oplus 2 = 1$,排列变为 $[3, 2, 1]$,达成目标。