分数: 600 点
问题陈述
AtCoder 的总部包括 N 房间编号 1 to N。对于任意两个房间,都有一条直接的通道连接这些房间。
出于安全考虑,高桥社长要求你设置一个 级别 对于每一段,它是一个正整数,并且必须满足以下条件:
- 对于每个房间 i\ (1 \leq i \leq N),如果我们离开房间 i,穿过一些等级相同的通道,回到房间 i,我们经过一段通道的次数总是偶数。
您的任务是设置段落的级别,以使段落的最高级别最小化。
约束
- N 是介于 2 和 500 (含)。
输入
输入由标准输入按以下格式给出:
N
输出
打印一种为段落设置级别的方法,以便实现目标,如下所示:
a_{1,2} a_{1,3} ... a_{1,N}
a_{2,3} ... a_{2,N}
.
.
.
a_{N-1,N}
这里 a_{i,j} 是连接房间的通道的层数 i 和房间 j.
如果有多个解决方案,则接受其中任何一个。
示例输入 1
3
示例输出 1
1 2 1
下图描述了此输出:

例如,如果我们离开房间 2,遍历路径 2 \to 3 \to 2 \to 3 \to 2 \to 1 \to 2 只通过关卡通道 1 并返回房间 2,我们通过一个通道六次。