← 返回题目列表

Codeforces · 1583/F

F. 童年梦想的捍卫者

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

即使你不理会它们,它们也会自行碎裂。所以,总得有人保护他们吧?

你发现自己又在璃月城里和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

注意

第一个测试用例的相应结构如下所示:

第二个测试用例的相应结构如下所示: