并查集(set)

【题目描述】

对于一个长度为 $n$ 值域为 $[1,n]\cap Z$ 的数组 $f$，定义以下两个操作：

1. 有返回值的 $find(x)$ 操作（$1 \le x \le n$）：
   • 若 $f_x = x$：返回 $x$；
   • 否则，返回进行 $find(f_x)$ 操作并将返回值记为 $root$，令 $f_x \gets root$，并返回 $root$。
2. 无返回值的 $merge(x,y)$ 操作（$1 \le x,y \le n$）：
   • 进行 $find(x)$ 操作并令返回值为 $x'$，进行 $find(y)$ 操作并令返回值为 $y'$；
   • 若 $f_{x'} \ne f_{y'}$，让 $f_{x'} \gets y'$。

给定两个长度为 $n$ 的数组 $a$ 和 $b$，能否通过 $2\times n^2$ 次以内的上述两个操作将 $a$ 变成 $b$，若可行给出构造方案（保证 $a$，$b$ 都可以从一个 $\forall b_i=i$ 的数组通过若干次上述操作得到）

【输入格式】

本题单个测试点有多组测试数据。

从 set.in 输入数据。

第一行一个整数 $T$ 表示数据组数。

对于每组数据：

第一行一个整数 $n$。

接下来一行 $n$ 个整数表示 $a$。

接下来一行 $n$ 个整数表示 $b$。

【输出格式】

输出数据到 set.out。

对于每组数据，若无法满足则输出一行 NO。

否则，第一行输出 YES。

接下来一行一个整数 $m$ 表示你的操作次数。

接下来 $m$ 行每行表示操作，每个操作按一下方式输出：

• 1 x：调用 $find(x)$；
• 2 x y：调用 $merge(x,y)$。

如果有多种方案请输出任意一种。

【样例 1 输入】

5
3
1 2 3
2 2 3
4
1 2 3 3
1 1 1 2
5
1 2 3 4 5
2 3 4 5 5
5
1 1 1 1 1
1 2 3 4 5
6
1 2 2 4 5 6
1 1 5 1 4 2

【样例 1 输出】

YES
1
2 1 2
YES
4
2 3 2
1 4
2 2 1
1 3
YES
4
2 1 2
2 1 3
2 2 4
2 3 5
NO
YES
7
2 6 2
2 2 5
1 3
2 2 4
1 2
2 2 1
1 2

【样例 2】

见选手目录下的 set/set2.in 与 set/set2.ans。

该样例满足测试点 $1$ 的约束条件。

【样例 3】

见选手目录下的 set/set3.in 与 set/set3.ans。

该样例满足测试点 $8,9,10$ 的约束条件。

【数据范围】

对于 $100\%$ 的数据，满足 $1 \le T \le 10^5$，$1 \le n \le 1000$，$\sum n^2 \le 5 \times 10^6$，$\forall a_i \in [1,n]$，$\forall b_i \in [1,n]$。

【提示】

下发了个 checker.cpp，保证与评测使用的完全不相同，不保证能正常运行。一般上是这么用的：

打开 powershell，进入当前文件夹；

编译：g++ checker.cpp -o checker -std=c++14 -Wall -O2；

运行：./checker set.in set.out set.ans ，set.in 是输入文件，set.out 是输出文件，set.ans 是答案文件。

过了会输出 AC，没过不会输出 AC。