#P18247. Permutation Routing
Permutation Routing
Permutation Routing
题目描述
Bobo 有一棵包含 个顶点的树,顶点编号为 。初始时,顶点 上的数字为 ,其中 是 到 的一个排列。
一次操作中,Bobo 可以选择树的一个匹配 ,并对 中的每条边 ,交换顶点 与顶点 上的数字。匹配指的是:所选边中,任意两条边都没有公共端点。因此,这些交换可以在同一轮中同时进行。
请构造一个至多包含 次操作的方案,使所有顶点最终满足 。
你不需要最小化操作次数。合法方案可以有多个,输出任意一个即可。
输入格式
第一行包含一个整数 ,表示测试数据组数。
对于每组数据:
- 第一行包含整数 。
- 第二行包含 个整数 ,表示初始排列。
- 接下来 行,每行包含两个整数 ,表示树的一条边。按照输入顺序,这些边的编号依次为 。
输出格式
对于每组数据:
第一行输出一个整数 ,满足 ,表示操作次数。
接下来输出 行。第 行先输出一个整数 ,满足 ;随后输出 个整数 ,表示本轮所选边在输入中的编号。
每轮选择的边必须构成匹配。按顺序执行所有操作后,必须对每个顶点 都有 。
允许选择空匹配,也允许在排列已经满足要求时输出 。
数据范围
- 。
- 。
- ,且 是一个排列。
- 每条边满足 且 ,给出的图是一棵树。
- 同一个输入文件中,所有测试数据的 之和不超过 。
样例
1
5
1 4 2 5 3
1 2
2 3
2 4
1 5
4
2 4 3
1 1
1 2
1 4