AT_tupc2022_g.All Pairs

给定一个正整数 $N$。长度为 $M$ 的正整数序列 $A$，若满足以下条件，则称为好序列：

• 对于任意整数对 $(x, y)$，$1 \leq x < y \leq N$，存在整数 $i\ (1 \leq i \leq M-1)$，使得 $(A_i, A_{i+1}) = (x, y)$ 或 $(A_i, A_{i+1}) = (y, x)$。

请在长度最短的好序列中，输出字典序最小的那一个。

给定 $T$ 组测试用例，请分别给出每组的答案。

输入以如下格式给出，从标准输入读入。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

每组用例按如下格式输入：

$N$

输出 $T$ 行。第 $i$ 行输出第 $i$ 个测试用例的答案，即数列 $A = (A_1, A_2, \ldots, A_M)$，用空格分隔，按顺序输出 $A_1, A_2, \ldots, A_M$。

样例解释 1

当 $N=3$ 时，例如 $A=(1,2,1,3,2)$ 是一个好序列，可以如下验证：

• 对于 $(x, y)=(1,2)$，有 $(A_1, A_2)=(x, y)$。
• 对于 $(x, y)=(1,3)$，有 $(A_3, A_4)=(x, y)$。
• 对于 $(x, y)=(2,3)$，有 $(A_4, A_5)=(y, x)$。

其他好序列还包括 $(1,2,3,1), (1,2,3,1,100), (3,1,2,3)$ 等。反之，$(1,2,3),(1,2,1,3)$ 不是好序列。

不存在长度不超过 $3$ 的好序列，因此长度为 $4$ 且字典序最小的好序列为 $(1,2,3,1)$。

数据范围

• $1\leq T\leq 99$
• $2\leq N\leq 100$
• 输入均为整数。

由 ChatGPT 5 翻译