← 返回题目列表

Codeforces · 755/E

E. 波兰球和白红图

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

PolishBall 有一个由 n 个顶点组成的无向简单图。不幸的是,它没有边缘。因此,该图非常令人悲伤。波兰球想让它更快乐,添加一些红色边缘。然后,他将在每个剩余的地方添加白色边缘。因此,最终的图形将是两种颜色的派系:白色和红色。

图的色彩度是一个值 min(dr, dw),其中 dr 是红色子图的直径,dw 是白色子图的直径。图的直径是最大值 d,使得其中某对顶点之间的最短路径等于 d。如果图不连通,我们认为它的直径为-1。

PolishBall 希望最终图表尽可能整洁。他希望最终的色彩度等于k。你能帮助他找到任何满足PolandBall要求的图表吗?

输入

唯一的一个输入行包含两个整数 n 和 k (2 ≤ n ≤ 1000, 1 ≤ k ≤ 1000),代表图形的大小和寻求的色彩。

输出

如果无法找到合适的图表,则打印 -1。

否则,您可以输出满足PolandBall要求的任何图表。首先,输出 m — 图中红边的数量。然后,你应该输出 m 行,每行包含两个整数 ai 和 bi,(1 ≤ ai,bi ≤ n,ai ≠ bi),这意味着顶点 ai 和 bi 之间有一条无向红边。每个红色边缘都应该打印一次,您可以按任意顺序打印边缘和每个边缘的顶点。

请记住,PolandBall 的图表应保持简单,因此不允许出现循环或多重边。

示例

输入 #1

4 1

输出 #1

-1

输入 #2

5 2

输出 #2

4
1 2
2 3
3 4
4 5

注意

在第一个示例案例中,没有图表可以满足PolandBall 的要求。

在第二个示例案例中,红色图是从 1 到 5 的路径。其直径为 4。但是,白色图的直径为 2,因为它由边 1-3、1-4、1-5、2-4、2-5、3-5 组成。