你需要编写一个集群管理器扩展来提升产品性能。你的产品拥有 $n$ 个服务（编号从 $1$ 到 $n$），部署在一个包含 $2n$ 台机器（编号从 $1$ 到 $2n$）的集群上。每个服务恰好运行两个副本。每台机器恰好运行某个服务的一个副本。

集群性能的关键因素之一是网络。部分机器对之间有直接连接，可以非常高效地传输数据。集群中共有 $2n - 1$ 条直接连接，且任意两台机器之间都可以通过直接连接进行数据传输。换句话说，这些直接连接构成了一棵树。

在部署期间，所有 $2n$ 个副本已被分配到各台机器上。你的扩展程序会获取直接连接列表以及序列 $a_1, a_2, \dots, a_{2n}$，其中 $a_i$ 表示将在机器 $i$ 上运行的服务编号。你的扩展程序可以交换机器之间的部分副本。交换操作选取两台机器 $i, j$，并交换 $a_i$ 和 $a_j$ 的值。每台机器最多只能参与一次交换操作。你的扩展程序应执行若干次交换操作，以使集群性能最大化。

由于大部分数据是在同一服务的两个副本之间传输的，因此集群性能定义为：两个副本运行在直接相连的机器上的服务数量。请编写该扩展程序以最大化集群性能。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。

第二行包含 $2n$ 个整数 $a_1, a_2, \dots, a_{2n}$ ($1 \le a_i \le n$)。保证序列中 $1$ 到 $n$ 的每个值恰好出现两次。

接下来的 $2n - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le 2n, u \neq v$)，表示机器 $u$ 和 $v$ 之间有直接连接。保证直接连接构成一棵树。

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

输出格式

对于每个测试用例，第一行输出一个整数 $k$ ($0 \le k \le n$)，表示你希望执行的交换操作次数。

接下来的 $k$ 行，每行包含两个整数 $i, j$ ($1 \le i, j \le 2n, i \neq j$)，表示一次交换操作。每个编号 $1$ 到 $2n$ 在输出中最多出现一次。

注意操作顺序并不重要。应用交换操作后，集群性能应达到最大值。你可以输出任何满足要求的答案。

样例

样例输入 1

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
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。显然，该用例的性能无法进一步提升。