← 返回题目列表

AtCoder · arc220_d

D. 长路

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

分数: 800 点

问题陈述

给你一个正整数 N.

让 G 是一个完整的无向图 N 顶点 1,2,\ldots,N 和 \displaystyle \frac{N(N-1)}2 边缘。

寻找踪迹 (v_1,v_2,\ldots,v_k) on G 满足以下所有条件。

  • 对于所有整数 i 这样 1 \leq i \leq k-2, |v_i - v_{i+2}| = 1
  • \displaystyle \frac{(N-2)^2}2 \le k

可以证明,这样的踪迹在约束条件下总是存在的。

什么是踪迹? 顶点序列 无向图上的 (v_1,v_2,\ldots,v_k) 在无向图上 G 被称为踪迹 G 如果满足以下所有条件。
  • 1\le v_i\le N.
  • 对于 1\le i\le k-1,存在连接顶点的边 v_i 和 v_{i+1}.
  • 对于 1\le i < j \le k-1,连接顶点的边 v_i 和 v_{i+1} 和连接顶点的边 v_j 和 v_{j+1} 是不同的。

约束

  • 1\le T\le 50
  • 3\le N\le 1000
  • 总和 N 所有测试用例最多 1000.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

每个测试用例均按以下格式给出:

N

输出

按顺序输出测试用例的答案,以换行符分隔。

对于每个测试用例,输出一条线索 (v_1,v_2,\ldots,v_k) on G 满足以下格式的所有条件:

k
v_1 v_2 \ldots v_k

如果有多个路径 G 满足所有条件均存在,其中任何一个都将被接受。


示例输入 1

2
3
5

示例输出 1

3
1 3 2
5
2 1 3 2 4

考虑第一个测试用例。

对于 (v_1,v_2,v_3)=(1,3,2),

  • |v_1-v_3|=|1-2|=1
  • \displaystyle \frac{(N-2)^2}2=\frac12\le 3
  • 连接顶点的边 1 和 3 和连接顶点的边 3 和 2 是不同的。

因此,我们可以确认样本输出是满足所有条件的轨迹。

例如,也接受以下输出:

4
2 3 1 2