P12104 [NERC2024] Managing Cluster

你打算开发一个集群管理扩展，以提升产品性能。你的产品包含 $n$ 个服务（编号从 $1$ 到 $n$），运行在一个拥有 $2n$ 台机器（编号从 $1$ 到 $2n$）的集群上。每个服务运行恰好两个副本，每个副本部署在某台机器上。每台机器恰好运行一个服务的副本。 这个集群性能的关键因素之一是网络结构。一些机器之间存在直接连接，能够高效传输数据。一共存在 $2n - 1$ 条直接连接，并且任意两台机器之间都可以通过这些连接实现通信。换句话说，这些直接连接构成了一棵树。 部署过程中，$2n$ 个副本已分配到机器。你的扩展程序将获取所有直接连接的信息，以及一个长度为 $2n$ 的序列 $a_1,a_2,\ldots,a_{2n}$，其中 $a_i$ 表示第 $i$ 台机器上运行的服务编号。 你的程序可以对副本进行交换操作。一次交换操作选定两台机器 $i$ 和 $j$，交换 $a_i$ 和 $a_j$ 的值。每台机器最多参与一次交换操作。 你需要设计一组交换操作，以使集群性能最大化。 由于同一服务的两个副本之间的数据交换最为频繁，集群性能定义为：有多少个服务的两个副本位于一对直接连接的机器上。 请你编写程序，输出一组交换操作，使得集群性能最大。

第一行包含一个整数 $T\;(1 \leq T \leq 10^5)$，表示测试用例的数量。 每组测试用例包括如下内容： - 第一行一个整数 $n\;(1 \leq n \leq 10^5)$，表示服务数量； - 第二行 $2n$ 个整数 $a_1,a_2,\ldots,a_{2n}$（$1 \leq a_i \leq n$），表示每台机器当前运行的服务编号。保证每个服务编号出现恰好两次； - 接下来的 $2n - 1$ 行，每行两个整数 $u,v$（$1 \leq u,v \leq 2n$，$u \ne v$），表示第 $u$ 台机器与第 $v$ 台机器之间存在直接连接。保证这些连接构成一棵树。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试用例： - 第一行输出一个整数 $k\;(0 \leq k \leq n)$，表示进行的交换操作次数； - 接下来的 $k$ 行，每行输出两个整数 $i$ 和 $j$（$1 \leq i,j \leq 2n$，$i \ne j$），表示将第 $i$ 台机器和第 $j$ 台机器上的服务副本进行交换。注意，每台机器至多参与一次交换。 交换操作的顺序无关紧要。交换完成后，集群性能必须达到最大。输出任意一组满足条件的解均可。

在第一个测试用例中，只有服务 $2$ 的两个副本处于相邻的机器上，因此性能为 $1$。通过交换机器 $1$ 和 $3$ 上的副本，可以使服务 $1$ 和服务 $2$ 的副本都位于相邻机器上，性能提升至 $2$。  在第二个测试用例中，没有任何服务的副本处于相邻机器上，初始性能为 $0$。通过交换 $(1,5)$，$(8,3)$ 和 $(4,7)$ 三对机器，可以让服务 $2$、$3$ 和 $4$ 的副本分别配对，从而性能提升到 $3$。可以证明此时无法再提升至 $4$。  在第三个测试用例中，只有服务 $1$ 的两个副本在相邻机器上，性能为 $1$，且无法进一步提升。