Shiratama
给定 1,2,…,2n 的一个排列 p1,p2,…,p2n。允许执行两类操作:
- 对所有奇数位置 i=1,3,…,2n−1,同时交换 pi 与 pi+1。
- 选择一个偶数位置 i∈{2,4,…,2n},交换 pi 与 pi+1。这里规定 p2n+1=p1。
请使用不超过 2n 次操作 1,且不超过 2n2 次操作 2,将排列变为 1,2,…,2n。如果无法做到,报告无解。
输入格式
第一行是测试用例数 t,1≤t≤105。
每组用例第一行包含 n,第二行包含排列的 2n 个元素。
1≤n≤100;所有用例的 ∑n2≤106。
输出格式
无解时输出一行 NO。
否则输出三行:第一行 YES;第二行总操作数 k;第三行 k 个整数 a1,…,ak。
- aj=1 表示执行操作 1;
- aj∈{2,4,…,2n} 表示执行操作 2,选择位置 aj。
必须分别满足两类操作的次数限制,因此也有 0≤k≤2n2+2n。k=0 时第三行可以为空。有多种合法方案时输出任意一种。
样例 1
3
2
1 3 4 2
2
2 4 1 3
3
1 2 4 3 5 6
NO
YES
2
2 1
YES
7
2 4 1 6 1 2 4