← 返回题目列表

Codeforces · 1944/A

A. 摧毁桥梁

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

有 $$$n$$$ 个岛屿,编号为 $$$1、2、\ldots、n$$$。最初,每对岛屿都通过一座桥梁连接起来。因此,总共有 $$$\frac{n (n - 1)}{2}$$$ 桥。

Everule 住在 $$$1$$$ 岛上,喜欢通过桥梁游览其他岛屿。统治者有能力摧毁最多$$$k$$$桥梁,以最大限度地减少Everule可以使用(可能是多个)桥梁到达的岛屿数量。

找出如果统治者以最佳方式摧毁桥梁,Everule 可以访问的最小岛屿数量(包括岛屿 $$$1$$$)。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 100$$$, $$$0 \le k \le \frac{n \cdot (n - 1)}{2}$$$)。

输出

对于每个测试用例,输出如果 Dominer 以最佳方式摧毁桥梁,Everule 可以访问的最小岛屿数量。

示例

输入 #1

6
2 0
2 1
4 1
5 10
5 3
4 4

输出 #1

2
1
4
1
5
1

注意

在第一个测试用例中,由于无法摧毁任何桥梁,因此所有岛屿都可以到达。

在第二个测试用例中,您可以摧毁 $$$1$$$ 岛和 $$$2$$$ 岛之间的桥梁。 Everule 将无法访问 $$$2$$$ 岛,但仍可以访问 $$$1$$$ 岛。因此,Everule 可以访问的岛屿总数为 $$$1$$$。

在第三个测试用例中,无论 Dominer 做什么,Everule 总是有办法到达所有岛屿。例如,如果统治者摧毁了$$$1$$$和$$$2$$$之间的桥梁,Everule仍然可以通过$$$1 \to 3 \to 2$$$访问$$$2$$$岛,因为$$$1$$$和$$$3$$$之间以及$$$3$$$和$$$2$$$之间的桥梁没有被摧毁。

在第四个测试用例中,您可以销毁自 $$$k = \frac{n \cdot (n - 1)}{2}$$$ 以来的所有桥梁。 Everule 将只能访问 $$$1$$$ 岛(island $$$1$$$)。