Имеется \(n\) островов, пронумерованных \(1, 2, \ldots, n\). Изначально каждая пара островов соединена мостом. Таким образом, всего существует \(\frac{n (n - 1)}{2}\) мостов.
Эверул живет на острове \(1\) и с удовольствием посещает другие острова, используя мосты. Доминатор может уничтожить не более \(k\) мостов, чтобы минимизировать количество островов, на которые Эверул может попасть, пройдя по оставшимся (возможно, нескольким) мостам.
Найдите минимальное количество островов (включая остров \(1\)), которые Эверул может посетить, если Доминатор разрушит мосты оптимально.
Выходные данные
Для каждого набора входных данных выведите минимальное количество островов, которые может посетить Эверул, если Доминатор разрушит мосты оптимально.
Примечание
В первом наборе входных данных, поскольку ни один мост не может быть разрушен, все острова будут доступны.
Во втором наборе входных данных вы можете уничтожить мост между островами \(1\) и \(2\). Эверул не сможет посетить остров \(2\), но сможет посетить остров \(1\). Таким образом, общее количество островов, которые может посетить Эверул, равняется \(1\).
В третьем наборе входных данных Эверул всегда имеет возможность добраться до всех островов, вне зависимости от действий Доминатора. Например, если Доминатор разрушит мост между островами \(1\) и \(2\), Эверул все равно может посетить остров \(2\), путешествуя по пути \(1 \to 3 \to 2\), так как мосты между \(1\) и \(3\), а также между \(3\) и \(2\) не разрушены.
В четвертом наборе входных данных можно уничтожить все мосты, так как \(k = \frac{n \cdot (n - 1)}{2}\). Эверул сможет посетить только \(1\) остров (остров \(1\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2 0
2 1
4 1
5 10
5 3
4 4
|
2
1
4
1
5
1
|