分数: 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