P12939 [NERC 2019] Foolprüf Security

Alice 和 Bob 获得了一份秘密地下设施的地图。该设施由 $n$ 个**安全单元**和 $m$ 个**化学实验室**组成，通过双向隧道连接。该设施的地图构成一棵**树**：共有 $n + m - 1$ 条隧道，且不存在环路。安全单元对应的顶点编号为 $1$ 至 $n$，化学实验室的编号为 $n+1$ 至 $n+m$。每条隧道连接一个安全单元和一个化学实验室；不存在连接两个安全单元或两个化学实验室的隧道。 为了防止 Alice 或 Bob 被捕，他们决定将地图分成两部分。为此，他们计算了这棵树的 **Prüfer 编码**。Alice 随后将原始编码中 $1$ 至 $n$ 的部分数字按顺序保存到她的数据存储中，Bob 则保存了 $n+1$ 至 $n+m$ 的部分数字，同样按原始编码的顺序存储。 一棵 $k$ 个顶点的树的 Prüfer 编码是一个长度为 $k - 2$ 的序列，其中每个数字的取值范围是 $1$ 至 $k$，构造方式如下：找到标号最小的叶子节点（度数为 1 的顶点），将其从树中移除，并记录其唯一邻居的标号。重复此过程 $k - 3$ 次，直到只剩一条边。记录的 $k - 2$ 个顶点标号序列即为 Prüfer 编码。 Alice 和 Bob 安全返回后，准备将他们的数据合并以恢复原始地图。但他们在备份时可能出错，导致不存在符合条件的地图。他们需要你的帮助来恢复任意一种可能的地图，使得 Alice 和 Bob 保存的部分都是该地图 Prüfer 编码的子序列。

输入的第一行包含四个整数 $n$、$m$、$k_a$ 和 $k_b$（$2 \le n, m \le 10^5$；$1 \le k_a, k_b$；$k_a + k_b \le n + m - 2$）。 第二行包含 $k_a$ 个整数 $a_1, a_2, \ldots, a_{k_a}$（$1 \le a_i \le n$）——Alice 保存的地图部分。 第三行包含 $k_b$ 个整数 $b_1, b_2, \ldots, b_{k_b}$（$n + 1 \le b_i \le n + m$）——Bob 保存的地图部分。

如果不存在符合条件的地图，输出 $\tt{No}$。 否则，第一行输出 $\tt{Yes}$，随后输出 $n + m - 1$ 行描述可能的地图。每行包含两个整数 $u_i$ 和 $v_i$，表示设施的第 $i$ 条隧道连接的安全单元和化学实验室。

第一个示例中树的 Prüfer 编码为 $(\underline{7}, \mathbf{1}, 6, \mathbf{3}, \mathbf{3}, \underline{8}, \mathbf{4})$。  翻译由 DeepSeek V3 完成