M. 管理集群（）

• 时间限制： 3 秒
• 内存限制： 1024 MB
• 参考难度： Codeforces 2700
• 判题方式： 特殊判题

题目描述

你准备编写一个集群管理器扩展，以提高产品性能。

产品包含 $n$ 个服务，编号为 $1$ 到 $n$，部署在一个由 $2n$ 台机器组成的集群上，机器编号为 $1$ 到 $2n$。

每个服务恰好运行两个副本，每个副本运行在某一台机器上；每台机器恰好运行一个服务副本。

集群性能的一个关键因素是网络连接。有些机器对之间存在直接连接，可以非常高效地传输数据。直接连接总数恰好为 $2n-1$，并且任意两台机器之间都可以通过若干直接连接互相到达。换言之，机器之间的直接连接构成一棵树。

部署完成后，所有 $2n$ 个副本已经分配到机器上。扩展程序获得：

• 直接连接列表；
• 序列 $a_1,a_2,\ldots,a_{2n}$，其中 $a_i$ 表示机器 $i$ 上运行的服务编号。

扩展程序可以交换不同机器上的副本。一次交换操作选择两台机器 $i,j$，交换 $a_i$ 和 $a_j$。

每台机器最多参与一次交换操作。

由于同一服务的两个副本之间会传输大量数据，集群性能定义为：

两个副本运行在直接相连机器上的服务数量。

请输出若干交换操作，使最终集群性能最大。

输入格式

第一行包含测试用例数量 $T$：

对于每个测试用例：

第一行包含整数 $n$：

第二行包含 $2n$ 个整数

其中 $1\le a_i\le n$。保证每个 $1$ 到 $n$ 的服务编号在序列中恰好出现两次。

接下来 $2n-1$ 行，每行包含两个整数 $u,v$：

表示机器 $u$ 和机器 $v$ 直接相连。

保证所有直接连接构成一棵树。

所有测试用例的 $n$ 之和不超过 $10^5$。

输出格式

对于每个测试用例，先输出一行整数 $k$：

表示交换操作的数量。

接下来 $k$ 行，每行输出两个整数 $i,j$，表示交换机器 $i$ 与机器 $j$ 上的副本。

每个 $1$ 到 $2n$ 的机器编号在所有交换操作中至多出现一次。

交换操作的执行顺序不重要。执行全部操作后，集群性能必须达到最大值。

若有多种合法方案，输出任意一种。

样例

3
2
1 2 2 1
1 2
2 3
3 4
4
4 3 1 3 2 4 1 2
1 2
3 1
3 4
5 1
5 6
2 7
2 8
3
1 1 2 2 3 3
1 2
1 3
1 4
1 5
1 6

1
1 3
3
1 5
8 3
4 7
0

样例说明

第一组数据中，初始时只有服务 2 的两个副本位于直接相连的机器上，因此性能为 1。交换机器 1 和机器 3 上的副本后，性能可以提高到 2。

第二组数据中，初始时没有任何服务的两个副本位于直接相连的机器上，性能为 0。执行交换 1 5、8 3 和 4 7 后，服务 2、3、4 的两个副本均位于直接相连的机器上，性能提高到 3。可以证明无法达到 4。

第三组数据中，只有服务 1 的两个副本位于直接相连的机器上，因此性能为 1，并且不可能进一步提高。