311169: CF1944A. Destroying Bridges
Description
There are $n$ islands, numbered $1, 2, \ldots, n$. Initially, every pair of islands is connected by a bridge. Hence, there are a total of $\frac{n (n - 1)}{2}$ bridges.
Everule lives on island $1$ and enjoys visiting the other islands using bridges. Dominater has the power to destroy at most $k$ bridges to minimize the number of islands that Everule can reach using (possibly multiple) bridges.
Find the minimum number of islands (including island $1$) that Everule can visit if Dominater destroys bridges optimally.
InputEach test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of test cases. The description of the test cases follows.
The first and only line of each test case contains two integers $n$ and $k$ ($1 \le n \le 100$, $0 \le k \le \frac{n \cdot (n - 1)}{2}$).
OutputFor each test case, output the minimum number of islands that Everule can visit if Dominater destroys bridges optimally.
ExampleInput6 2 0 2 1 4 1 5 10 5 3 4 4Output
2 1 4 1 5 1Note
In the first test case, since no bridges can be destroyed, all the islands will be reachable.
In the second test case, you can destroy the bridge between islands $1$ and $2$. Everule will not be able to visit island $2$ but can still visit island $1$. Therefore, the total number of islands that Everule can visit is $1$.
In the third test case, Everule always has a way of reaching all islands despite what Dominater does. For example, if Dominater destroyed the bridge between islands $1$ and $2$, Everule can still visit island $2$ by traveling by $1 \to 3 \to 2$ as the bridges between $1$ and $3$, and between $3$ and $2$ are not destroyed.
In the fourth test case, you can destroy all bridges since $k = \frac{n \cdot (n - 1)}{2}$. Everule will be only able to visit $1$ island (island $1$).
Output
有n个岛屿，编号为1, 2, ..., n。起初，每对岛屿之间都有一座桥连接，总共有n(n - 1)/2座桥。Everule住在岛屿1上，喜欢通过桥去访问其他岛屿。Dominater有能力摧毁最多k座桥，以最小化Everule可以通过（可能是多座）桥到达的岛屿数量。求如果Dominater最优地摧毁桥梁，Everule能访问的岛屿的最小数量（包括岛屿1）。
输入数据格式：
每个测试包含多个测试案例。第一行包含一个整数t（1 ≤ t ≤ 10^3）——测试案例的数量。接下来是每个测试案例的描述。
每个测试案例的第一行（也是唯一一行）包含两个整数n和k（1 ≤ n ≤ 100，0 ≤ k ≤ n(n - 1)/2）。
输出数据格式：
对于每个测试案例，输出如果Dominater最优地摧毁桥梁，Everule能访问的岛屿的最小数量。
注意：
在第一个测试案例中，由于不能摧毁任何桥梁，所有岛屿都是可到达的。
在第二个测试案例中，你可以摧毁岛屿1和岛屿2之间的桥梁。Everule将无法访问岛屿2，但仍然可以访问岛屿1。因此，Everule可以访问的岛屿总数是1。
在第三个测试案例中，无论Dominater如何行动，Everule总是有办法到达所有岛屿。例如，如果Dominater摧毁了岛屿1和岛屿2之间的桥梁，Everule仍然可以通过1 → 3 → 2的路径访问岛屿2，因为岛屿1和岛屿3之间以及岛屿3和岛屿2之间的桥梁没有被摧毁。
在第四个测试案例中，由于k = n(n - 1)/2，你可以摧毁所有桥梁。Everule将只能访问1个岛屿（岛屿1）。题目大意： 有n个岛屿，编号为1, 2, ..., n。起初，每对岛屿之间都有一座桥连接，总共有n(n - 1)/2座桥。Everule住在岛屿1上，喜欢通过桥去访问其他岛屿。Dominater有能力摧毁最多k座桥，以最小化Everule可以通过（可能是多座）桥到达的岛屿数量。求如果Dominater最优地摧毁桥梁，Everule能访问的岛屿的最小数量（包括岛屿1）。 输入数据格式： 每个测试包含多个测试案例。第一行包含一个整数t（1 ≤ t ≤ 10^3）——测试案例的数量。接下来是每个测试案例的描述。 每个测试案例的第一行（也是唯一一行）包含两个整数n和k（1 ≤ n ≤ 100，0 ≤ k ≤ n(n - 1)/2）。 输出数据格式： 对于每个测试案例，输出如果Dominater最优地摧毁桥梁，Everule能访问的岛屿的最小数量。 注意： 在第一个测试案例中，由于不能摧毁任何桥梁，所有岛屿都是可到达的。 在第二个测试案例中，你可以摧毁岛屿1和岛屿2之间的桥梁。Everule将无法访问岛屿2，但仍然可以访问岛屿1。因此，Everule可以访问的岛屿总数是1。 在第三个测试案例中，无论Dominater如何行动，Everule总是有办法到达所有岛屿。例如，如果Dominater摧毁了岛屿1和岛屿2之间的桥梁，Everule仍然可以通过1 → 3 → 2的路径访问岛屿2，因为岛屿1和岛屿3之间以及岛屿3和岛屿2之间的桥梁没有被摧毁。 在第四个测试案例中，由于k = n(n - 1)/2，你可以摧毁所有桥梁。Everule将只能访问1个岛屿（岛屿1）。