← 返回题目列表

AtCoder · arc189_e

E. 直线路径

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

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