AT_arc220_d [ARC220D] Long Trail

给定一个正整数 $N$。 设 $G$ 是一个有 $N$ 个顶点 $1,2,\ldots,N$ 的无向完全图，共有 $\frac{N(N-1)}2$ 条边。 请在图 $G$ 上找到一条序列 $(v_1,v_2,\ldots,v_k)$，使其满足如下所有条件： - 对于所有满足 $1 \leq i \leq k-2$ 的整数 $i$，都有 $|v_i - v_{i+2}| = 1$。 - $k \geq \frac{(N-2)^2}{2}$。 可以证明，在给定的限制条件下，总能找到满足要求的路径。 什么是 trail？在一个无向图 $G$ 上，若一条顶点序列 $(v_1,v_2,\ldots,v_k)$ 满足以下所有条件，则称其为 trail： - $1 \leq v_i \leq N$； - 对于 $1 \leq i \leq k-1$，顶点 $v_i$ 与 $v_{i+1}$ 间存在一条边； - 对于 $1 \leq i < j \leq k-1$，边 $(v_i, v_{i+1})$ 与边 $(v_j, v_{j+1})$ 不相同。

输入来自标准输入，格式如下： > $T$ $\text{case}_1$ $\text{case}_2$ $\vdots$ $\text{case}_T$ 每组测试用例如下格式： > $N$

按测试用例顺序输出答案，每组用换行分隔。 对每组测试用例，输出一条在 $G$ 上满足所有条件的 trail $(v_1, v_2, ..., v_k)$，格式如下： > $k$ $v_1$ $v_2$ $\ldots$ $v_k$ 若有多组满足条件的 trail，任意一种均可。

### 样例解释 1 考虑第一个样例测试用例。 对于 $(v_1,v_2,v_3) = (1,3,2)$： - $|v_1-v_3|=|1-2|=1$； - $\frac{(N-2)^2}{2} = \frac{1}{2} \leq 3$； - 边 $(1,3)$ 与边 $(3,2)$ 不相同。 因此，该输出为一条满足条件的 trail。 例如，下列输出也是可行的： ``` 4 2 3 1 2 ``` ### 数据范围 - $1 \leq T \leq 50$ - $3 \leq N \leq 1000$ - 所有测试用例中 $N$ 之和不超过 $1000$。 - 所有输入值均为整数。 由 ChatGPT 5 翻译