#P17942. Shiratama

Shiratama

Shiratama

给定 1,2,…,2n1,2,\ldots,2n 的一个排列 p1,p2,…,p2np_1,p_2,\ldots,p_{2n}。允许执行两类操作:

  1. 对所有奇数位置 i=1,3,…,2n−1i=1,3,\ldots,2n-1,同时交换 pip_i 与 pi+1p_{i+1}。
  2. 选择一个偶数位置 i∈{2,4,…,2n}i\in\{2,4,\ldots,2n\},交换 pip_i 与 pi+1p_{i+1}。这里规定 p2n+1=p1p_{2n+1}=p_1。

请使用不超过 2n2n 次操作 1,且不超过 2n22n^2 次操作 2,将排列变为 1,2,…,2n1,2,\ldots,2n。如果无法做到,报告无解。

输入格式

第一行是测试用例数 tt,1≤t≤1051\le t\le10^5。

每组用例第一行包含 nn,第二行包含排列的 2n2n 个元素。

1≤n≤1001\le n\le100;所有用例的 ∑n2≤106\sum n^2\le10^6。

输出格式

无解时输出一行 NO。

否则输出三行:第一行 YES;第二行总操作数 kk;第三行 kk 个整数 a1,…,aka_1,\ldots,a_k。

  • aj=1a_j=1 表示执行操作 1;
  • aj∈{2,4,…,2n}a_j\in\{2,4,\ldots,2n\} 表示执行操作 2,选择位置 aja_j。

必须分别满足两类操作的次数限制,因此也有 0≤k≤2n2+2n0\le k\le2n^2+2n。k=0k=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