AT_abc131_e [ABC131E] Friendships

题目描述

是否存在满足以下条件的 $N$ 个顶点的无向图？

• 图是简单且连通的。
• 每个顶点编号为 $1, 2, \ldots, N$。
• 设图的边数为 $M$，每条边编号为 $1, 2, \ldots, M$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$，每条边的长度为 $1$。
• 存在恰好 $K$ 对顶点对 $(i, j)\ (i < j)$，它们之间的最短距离为 $2$。

如果存在满足条件的图，请构造出其中一个。

输入格式

输入以以下格式从标准输入给出。

$N$ $K$

输出格式

如果不存在满足条件的图，输出 -1。

如果存在，输出其中一个满足条件的图，格式如下（符号含义见题目描述）：

$M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

如果存在多个满足条件的图，输出任意一个即可。

样例 1

输入

5 3

输出

5
4 3
1 2
3 1
4 5
2 3

样例 2

输入

5 8

输出

-1

说明/提示

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 100$
• $0 \leq K \leq \frac{N(N-1)}{2}$

样例解释 1

该图中，最短距离为 $2$ 的顶点对有 $(1, 4),\ (2, 4),\ (3, 5)$，共 $3$ 对，满足条件。

样例解释 2

不存在满足条件的图。

由 ChatGPT 4.1 翻译