即使你不理会它们,它们也会自行碎裂。所以,总得有人保护他们吧?
你发现自己又在璃月城里和Teucer一起玩了。当你带着这个古怪的小孩四处走动时,你会注意到这座城市的结构有些有趣。
璃月可以表示为包含$$$n$$$节点的有向图。节点的标记范围为 $$$1$$$ 到 $$$n$$$。当且仅当 $$$a < b$$$ 时,存在从节点 $$$a$$$ 到节点 $$$b$$$ 的有向边。
节点 $$$a$$$ 和 $$$b$$$ 之间的路径被定义为一系列边,这样您可以从 $$$a$$$ 开始,沿相应方向沿着所有这些边行进,并在 $$$b$$$ 结束。路径的长度由边的数量定义。长度为 $$$x$$$ 的彩虹路径被定义为图中的一条路径,使得 $$$x$$$ 边集中至少存在 2 种不同的颜色。
Teucer 最喜欢的号码是 $$$k$$$。您对以下场景感到好奇:如果要用颜色标记每条边,确保长度 $$$k$$$ 或更长的所有路径都是彩虹路径所需的最少颜色数是多少?
透克想要用璃月地图给他的哥哥一个惊喜。他还想知道使用最少颜色数量的有效边缘着色。请帮助他完成这项任务!
输入
输入的唯一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq k < n \leq 1000$$$)。
输出
在第一行,输出$$$c$$$,即满足上述要求所需的最小颜色。
在第二行,将有效的边缘着色打印为 $$$\frac{n(n-1)}{2}$$$ 整数数组,范围从 $$$1$$$ 到 $$$c$$$。结构中应该存在完全相同的 $$$c$$$ 不同颜色。首先按起始节点的升序打印边,然后按第二个节点打印边。
例如,如果 $$$n=4$$$,则边缘颜色将对应于以下边缘顺序:($$$1$$$, $$$2$$$), ($$$1$$$, $$$3$$$), ($$$1$$$, $$$4$$$), ($$$2$$$, $$$3$$$), ($$$2$$$, $$$4$$$), ($$$3$$$, $$$4$$$)
示例
输入 #1
5 3
输出 #1
2 1 2 2 2 2 2 2 1 1 1
输入 #2
5 2
输出 #2
3 3 2 2 1 2 2 1 3 1 1
输入 #3
8 7
输出 #3
2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
输入#4
3 2
输出#4
2 1 2 2
注意
第一个测试用例的相应结构如下所示:
第二个测试用例的相应结构如下所示: