分数: 800 点
问题陈述
标记完整图的边的方法之一 G 与 N 顶点为正整数,满足以下条件的图称为“好的完全图”。
- 不存在访问所有路径 N 顶点恰好一次,并且其边标签序列(按照边遍历的顺序)是非递减的。
判断是否存在良好的完整图。如果存在,则构造一个最小化分配给边缘的最大标签的标签。
约束
- 2 \leq N \leq 20
输入
输入由标准输入按以下格式给出:
N
输出
如果不存在良好的完整图,则打印 No.
如果存在,则按如下方式打印一个。让 a_{i,j} 是分配给连接顶点的无向边的标签 i 和 j.
Yes
a_{1,2} a_{1,3} a_{1,4} \dots a_{1,N}
a_{2,3} a_{2,4} \dots a_{2,N}
\vdots
a_{N-1,N}
如果存在多个解决方案,您可以打印其中任何一个。
示例输入 1
5
示例输出 1
Yes 2 1 4 4 4 3 1 1 3 2
例如,考虑按顺序访问顶点的路径 2, 5, 1, 4, 3。遍历的边标签的顺序为 (1, 4, 4, 1),这不是非递减的。
而且,不存在边标签序列非递减的路径,因此该图满足条件。
另外,当 N=5,不可能分配标签使得分配给边缘的最大标签为 3 或更少,因此该输出有效。
示例输入 2
2
示例输出 2
No