Friendships

题目描述

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

该图是简单且连通的。 顶点编号为 $1, 2, ..., N$。 令 $M$ 为图中的边数。边编号为 $1, 2, ..., M$，每条边的长度为 $1$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。 恰有 $K$ 对顶点 $(i,\ j)\ (i < j)$ 的最短距离为 $2$。

如果存在这样的图，请构造一个例子。

输入格式

从标准输入读取，格式如下： $N$ $K$

输出格式

如果不存在满足条件的无向图，输出 $-1$。 如果存在这样的图，请按以下格式输出一个例子（关于符号含义，参见题目描述）： $M$ $u_1$ $v_1$ : $u_M$ $v_M$

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

5 3

5
4 3
1 2
3 1
4 5
2 3

5 8

-1

提示

所有输入值均为整数。 $2 \leq N \leq 100$ $0 \leq K \leq \frac{N(N - 1)}{2}$该图有三对顶点的最短距离为 $2$：$(1,\ 4)$、$(2,\ 4)$ 和 $(3,\ 5)$。因此，条件被满足。
不存在满足条件的图。

标签: AtCoder|abc131E

来源

AtCoder|abc131E