G - All Pairs Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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) が求めるものです。