← 返回题目列表

AtCoder · abc131_e

E. 友谊

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

分数: 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

没有满足条件的图表。