分数: 500 点
问题陈述
是否存在无向图 N 顶点满足以下条件?
- 该图简单且连通。
- 顶点已编号 1, 2, ..., N.
- 让 M 是图中的边数。边缘已编号 1, 2, ..., M,每条边的长度为 1和边缘 i 连接顶点 u_i 和顶点 v_i.
- 正好有 K 顶点对 (i,\ j)\ (i < j) 使得它们之间的最短距离是 2.
如果存在这样的图,请构造一个示例。
约束
- 输入中的所有值都是整数。
- 2 \leq N \leq 100
- 0 \leq K \leq \frac{N(N - 1)}{2}
输入
输入由标准输入按以下格式给出:
N K
输出
如果不存在无向图 N 满足条件的顶点,打印 -1.
如果存在这样的图表,请按以下格式打印示例(有关符号代表的含义,请参阅问题陈述):
M u_1 v_1 : u_M v_M
如果存在多个满足条件的图,则接受其中任何一个。
示例输入 1
5 3
示例输出 1
5 4 3 1 2 3 1 4 5 2 3
该图有三对顶点,它们之间的最短距离是 2: (1,\ 4), (2,\ 4),和 (3,\ 5)。这样,条件就满足了。
示例输入 2
5 8
示例输出 2
-1
没有满足条件的图表。