#P18681. Disjoint Set Union

    ID: 18017 传统题 4000ms 1024MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-普通并查集路径压缩拓扑排序不变量分析直接模拟

Disjoint Set Union

Disjoint Set Union

最近,小青鱼正在学习并查集(DSU)。它是一种强大的数据结构,可以向图中加边,并判断两个顶点是否连通。

并查集维护由n个顶点组成的有根森林。每个顶点x(1≤x≤n)有唯一的父亲f[x];如果x=f[x],x就是所在树的根。最初每个顶点各自构成一棵树,即所有f[x]=x。

并查集有两种基本操作:

  • find(x):返回x所在树的根。
  • unite(x,y):先计算x′=find(x)、y′=find(y)。若x′=y′则不再合并;否则令f[x′]=y′。

为加速操作,小青鱼使用了路径压缩:每次调用find(x),都将从x到根路径上每个顶点的父亲直接改为该根。具体过程如下。注意即使unite的两点已经连通,也会先执行两次find所产生的路径压缩。

函数 find(f, x):
    如果 x = f[x]:
        返回 x
    f[x] ← find(f, f[x])
    返回 f[x]

过程 unite(f, x, y):
    x ← find(f, x)
    y ← find(f, y)
    如果 x ≠ y:
        f[x] ← y

小青鱼非常喜欢并查集。他从所有f[i]=i开始,进行了任意多次(也可以零次)以下操作:选择1≤x≤n并调用find(x),或者选择1≤x,y≤n并调用unite(x,y)。现在他将这些操作后的数组f交给你。

另给出长度同样为n的目标数组g。你希望继续使用上述并查集操作,将f变为g,即最后对每个1≤i≤n都有f[i]=g[i]。判断能否做到;若能,给出一组操作方案。

输入格式

第一行一个整数T(1≤T≤100000),表示测试用例数。每个测试用例:

  • 第一行一个整数n(3≤n≤1000)。
  • 第二行n个整数f1,…,fn,表示小青鱼操作后的父数组。保证f能由上述操作生成。
  • 第三行n个整数g1,…,gn,表示目标父数组。父亲编号对应1至n的顶点。

所有测试用例的n²之和不超过5000000。g可能不能由这些操作得到,需要由你的程序判断。

输出格式

对每个测试用例:若不能将f变为g,输出一行NO。否则:

  • 第一行输出YES。
  • 第二行输出整数m(0≤m≤2n²),表示操作数。
  • 接下来m行,每行输出一种操作:1 x表示调用find(x),2 x y表示调用unite(x,y)。操作中的顶点编号均须在1至n之间。

可以输出任意合法方案。可以证明:若存在方案,就存在操作数不超过2n²的方案。

样例输入

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

样例输出

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

样例输出为原题的一种合法方案,操作方案不唯一。本题采用精确特殊判题,不能按输出文本逐字比较。