题目理解

我们有两个长度为 $n$ 的数组 $a$ 和 $b$，可以对任意下标 $i$ 交换 $a_i$ 和 $b_i$ 任意次。定义 $f(c)$ 为数组 $c$ 中不同数字的个数，目标是最大化 $f(a) + f(b)$，并输出达到最大值时的两个数组。

关键观察

对于任意一个数值 $x$：

• 如果 $x$ 在 $a$ 和 $b$ 中都不出现，它对答案贡献为 $0$。
• 如果 $x$ 恰好出现一次，无论怎么操作，它一定出现在某个数组中，贡献为 $1$。
• 如果 $x$ 出现至少两次，它的贡献可以是 $1$ 或 $2$：
  • 如果所有出现都在同一个数组中，贡献为 $1$。
  • 如果两个数组都包含 $x$，贡献为 $2$。

设 $cnt_x$ 为 $x$ 在 $a$ 和 $b$ 中的总出现次数，那么 $x$ 对答案的贡献不超过 $\min(cnt_x, 2)$。

因此，答案的上界是：

并且这个上界是可以达到的。

建模为图论问题

对于每个下标 $i$，我们在 $a_i$ 和 $b_i$ 之间连一条无向边。这样得到一个图，顶点是数值（范围 $1$ 到 $2n$），边对应数组中的位置。

目标：给每条边定向（方向表示哪个值在 $a$ 中，哪个在 $b$ 中），使得：

• 对于度数 $\ge 2$ 的顶点，至少有一条出边（该值在 $a$ 中出现）。
• 对于度数 $\ge 2$ 的顶点，至少有一条入边（该值在 $b$ 中出现）。

如果满足这个条件，那么：

• 度数为 $0$ 的顶点：不影响答案。
• 度数为 $1$ 的顶点：唯一的一条边定向后，该值一定只出现在一个数组中，贡献 $1$。
• 度数 $\ge 2$ 的顶点：因为既有入边又有出边，该值一定在两个数组中都出现，贡献 $2$。

这样恰好达到上界 $\sum \min(cnt_x, 2)$。

构造方法

第一步：DFS 树定向

对每个连通分量，任选一个根做 DFS 树。

1. 将树边从上到下定向（从父节点指向子节点）。
2. 将返祖边（back edges）从下到上定向（从子节点指向祖先）。

这样处理后：

• 非根节点：因为有父节点指向它的树边，所以有入边；同时因为它至少有向子节点的边（或返祖边），所以有出边。条件满足。
• 根节点：可能有出边（指向子节点），但不一定有入边。如果根节点度数 $\ge 2$ 却没有返祖边进入它，则不满足条件。

第二步：处理根节点

如果根节点度数 $\ge 2$ 且没有返祖边进入它，那么它至少有 $2$ 个子树。选择其中一个子树，将该子树内所有边反向。这样：

• 根节点获得一条来自该子树的入边。
• 子树内的节点原本满足条件，反转后仍然满足（因为原先是双向的，反转后入边变出边，出边变入边，仍满足既有入边又有出边）。

第三步：实现细节

标程中分两次 DFS：

1. 第一次 DFS（used[v] > 0 的调用）：从度数为 $1$ 的顶点开始，保证这些端点被正确处理。
2. 第二次 DFS：处理剩余的连通分量（可能是环或没有度数为 $1$ 的点的分量），找到环上的一个起点（rt），然后从该点开始定向。

make 函数用于定向：如果位置 $i$ 还没被处理，就根据需要的方向交换 $a_i$ 和 $b_i$，并标记已处理。

算法复杂度

• 每个顶点（数值）最多有 $2n$ 个，每条边（下标）有 $n$ 条。
• 建图 $O(n)$。
• DFS 遍历 $O(n)$。
• 总复杂度 $O(n)$ 每个测试用例。

总结

这道题的核心是：

1. 推导出答案的上界 $\sum \min(cnt_x, 2)$。
2. 将问题转化为图的边定向问题，要求每个度数 $\ge 2$ 的顶点既有入边又有出边。
3. 用 DFS 树加特殊处理根节点的方法构造出达到上界的定向方案。