← 返回题目列表

AtCoder · tupc2022_g

G. 所有对

中文机器翻译题面 查看原题

配点 : 300 点

問題文

正整数 N 。长度 M 的正整数序列 给出了 A 满足以下条件时,良好的数列 我们称之为。

  • 任意整数的组合 (x,y) (1\leq x\lt y\leq N) , (A_i,A_{i+1})=(x,y) 或 至少 (A_i,A_{i+1})=(y,x) 的整数 选择 i\ (1\leq i\leq M-1) 存在。

长度 小于或等于 M 在最小的良好序列中,求字典序最小的序列。 请将

T 个测试用例,请分别求出答案。 包含在

制約

  • 1\leq T\leq 99
  • 2\leq N\leq 100
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

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

2
3
2

出力例 1

1 2 3 1
1 2

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) 就是所求的。