UOJ Logo Universal Online Judge

UOJ

#283. 直径拆除鸡

统计

正当计算鸡们还沉浸在过年的气氛中时,计算鸡村拉响了警报:远方来了一群程序猿。“他们又要来了!” 全村上下陷入了惊恐。

看过了有手撕鬼子情节的抗日神剧的直径拆除鸡不禁开起了脑洞。作为一种神奇的生物,每个程序猿都长得十分古怪。人的身体形状可以抽象为一个五角星型的 $6$ 个结点的树,而程序猿则可以长成任意一个 $n$ 个结点的树。那么,如果每次能拆除这棵树的直径,最多要花费多少时间才能把这棵树全部删除呢?

具体来说,直径拆除鸡脑补的是这样一个算法:

  • 输入一棵 $n$ 个结点的树,该算法进行过程中保证每时每刻保证图是一个森林
  • 令 $S = 0$,重复如下过程直到所有结点均被删除
    • 从图中任意找一个连通块,显然该连通块肯定是一棵树
    • 假设该树有 $t$ 个结点,执行 $S = S + t$
    • 从该树中找一条最长简单路,假设是从 $a$ 到 $b$。如果有多条那么选择 $a$ 最小的,当 $a$ 一样时选择 $b$ 最小的
    • 删除从 $a$ 到 $b$ 的简单路上的所有结点,包括 $a$ 和 $b$,这将导致该树结点会被删光或者分裂成一个或多个更小的树

计算次数即最后 $S$ 所存储的值。

现在,给你 $n, m$,请你构造一个包含 $n$ 个结点的树,且计算次数至少为 $m$,输入数据保证有解。

输入格式

一行,两个整数 $n, m$。保证 $n \ge 1, m \ge 0$。

输出格式

$n - 1$ 行,每行两个整数 $v, u$ 表示树上一条从 $v$ 到 $u$ 的边,需要满足 $1 \le v, u \le n$。

样例一

input

4 5

output

1 2
1 3
1 4

explanation

输出了一个包含 $(1, 2), (1, 3), (1, 4)$ 三条边的四个结点的树。第一次直径拆除鸡将删除从 $2$ 到 $3$ 的简单路径上的所有结点,即 $\{2, 1, 3\}$,删除后仅剩一个结点,再花费 $1$ 的计算次数将其删除。总共 $S = 4 + 1 = 5$。

另外还有一种四个结点的方案,边分别是 $(1, 2), (2, 3), (3, 4)$。这棵树的最长简单路为 $\{1, 2, 3, 4\}$,所以第一次删除后所有结点均会被删除,总计算次数为 $4$,无法满足 $S \ge m$ 的条件。

样例二

input

12 0

output

1 2
2 3
1 4
4 5
1 7
6 7
7 8
1 10
10 9
10 11
10 12

限制与约定

测试点编号 $n$ 其它限制
1$\leq 11$
2
3
4$= 1023$$m=3527$
5$= 1023$$m=11408$
6$= 4095$$m=93282$
7$\le 10000$
8
9
10

对于所有数据,保证 $0 \le m \le 10^9$ 且保证有解。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载