A7644. [ABC131E] Friendships
编程题
普及+/提高
知识点
题目描述
是否存在满足以下条件的 $N$ 个顶点的无向图？
- 图是简单且连通的。
- 每个顶点编号为 $1, 2, \ldots, N$。
- 设图的边数为 $M$，每条边编号为 $1, 2, \ldots, M$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$，每条边的长度为 $1$。
- 存在恰好 $K$ 对顶点对 $(i, j)\ (i < j)$，它们之间的最短距离为 $2$。
如果存在满足条件的图，请构造出其中一个。
- 图是简单且连通的。
- 每个顶点编号为 $1, 2, \ldots, N$。
- 设图的边数为 $M$，每条边编号为 $1, 2, \ldots, M$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$，每条边的长度为 $1$。
- 存在恰好 $K$ 对顶点对 $(i, j)\ (i < j)$，它们之间的最短距离为 $2$。
如果存在满足条件的图，请构造出其中一个。
输入格式
输入以以下格式从标准输入给出。
> $N$ $K$
> $N$ $K$
输出格式
如果不存在满足条件的图，输出
如果存在，输出其中一个满足条件的图，格式如下（符号含义见题目描述）：
> $M$
> $u_1$ $v_1$
> $u_2$ $v_2$
> $\vdots$
> $u_M$ $v_M$
如果存在多个满足条件的图，输出任意一个即可。
-1。如果存在，输出其中一个满足条件的图，格式如下（符号含义见题目描述）：
> $M$
> $u_1$ $v_1$
> $u_2$ $v_2$
> $\vdots$
> $u_M$ $v_M$
如果存在多个满足条件的图，输出任意一个即可。
输入输出样例
输入 #1
5 3
输出 #1
5 4 3 1 2 3 1 4 5 2 3
输入 #2
5 8
输出 #2
-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
不存在满足条件的图。
- 所有输入均为整数。
- $2 \leq N \leq 100$
- $0 \leq K \leq \frac{N(N-1)}{2}$
### 样例解释 1
该图中，最短距离为 $2$ 的顶点对有 $(1, 4),\ (2, 4),\ (3, 5)$，共 $3$ 对，满足条件。
### 样例解释 2
不存在满足条件的图。