#P18247. Permutation Routing

Permutation Routing

Permutation Routing

题目描述

Bobo 有一棵包含 nn 个顶点的树,顶点编号为 1,2,…,n1,2,\ldots,n。初始时,顶点 ii 上的数字为 pip_i,其中 p1,p2,…,pnp_1,p_2,\ldots,p_n 是 11 到 nn 的一个排列。

一次操作中,Bobo 可以选择树的一个匹配 MM,并对 MM 中的每条边 (u,v)(u,v),交换顶点 uu 与顶点 vv 上的数字。匹配指的是:所选边中,任意两条边都没有公共端点。因此,这些交换可以在同一轮中同时进行。

请构造一个至多包含 3n3n 次操作的方案,使所有顶点最终满足 pi=ip_i=i。

你不需要最小化操作次数。合法方案可以有多个,输出任意一个即可。

输入格式

第一行包含一个整数 TT,表示测试数据组数。

对于每组数据:

  • 第一行包含整数 nn。
  • 第二行包含 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n,表示初始排列。
  • 接下来 n−1n-1 行,每行包含两个整数 u,vu,v,表示树的一条边。按照输入顺序,这些边的编号依次为 1,2,…,n−11,2,\ldots,n-1。

输出格式

对于每组数据:

第一行输出一个整数 mm,满足 0≤m≤3n0\le m\le3n,表示操作次数。

接下来输出 mm 行。第 ii 行先输出一个整数 kik_i,满足 0≤ki<n0\le k_i<n;随后输出 kik_i 个整数 ti,1,…,ti,kit_{i,1},\ldots,t_{i,k_i},表示本轮所选边在输入中的编号。

每轮选择的边必须构成匹配。按顺序执行所有操作后,必须对每个顶点 ii 都有 pi=ip_i=i。

允许选择空匹配,也允许在排列已经满足要求时输出 m=0m=0。

数据范围

  • T≥1T\ge1。
  • 1≤n≤10001\le n\le1000。
  • 1≤pi≤n1\le p_i\le n,且 pp 是一个排列。
  • 每条边满足 1≤u,v≤n1\le u,v\le n 且 u≠vu\ne v,给出的图是一棵树。
  • 同一个输入文件中,所有测试数据的 n2n^2 之和不超过 10610^6。

样例

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