Background

Why is the rating 7?

Powerless: Equilibrium FTR 9.

Problem Description

The little robot is fishing for stars again.

The stars in the sky form several constellations. Each constellation has a “center point”. If a star loses its direct or indirect connection to the center point, then the star will detach from the constellation and fall to the ground.

After observing day and night, the little robot found the following properties of these constellations: each constellation is connected internally, and the number of connections among stars is always equal to the number of stars in that constellation.

Also, there are no connections between different constellations. Any two stars in the same constellation are connected directly or indirectly.

By observing celestial motion, he numbered the stars. He found that the center point of each constellation is the star with the smallest index in that constellation.

Unfortunately, the little robot can only obtain keys to remove these connections in a purely random way (diao yuan, “by fate”).

The little robot is very greedy and wants to get as many stars as possible in as little time as possible.

He wants $k$ stars. Can you tell him the minimum number of keys he needs to fish up?

If you solve this problem, maybe the little robot will give you some stars~

Simplified statement

Input Format

The first line contains two integers $n,k$, representing the total number of stars in the sky, the total number of connections between stars, and the number of stars the little robot wants to obtain.

Next, there are $n$ lines. Each line contains two integers $u,v$, indicating that there is a connection between star $u$ and star $v$.

It is guaranteed that within any constellation, the number of connections equals the number of stars. There are no self-loops, and there will not be two connections between the same pair of stars.

Output Format

Output one integer in a single line, representing the minimum number of keys the little robot needs to obtain enough stars.

4 1
1 2
2 3
3 1
1 4

1

17 9
1 2
1 6
1 3
3 4
4 5
5 6
6 7
8 10
10 9
10 11
11 12
11 13
13 14
14 8
15 13
8 16
16 17

3

Hint

This problem uses bundled tests.

Suppose there are $l$ constellations in total.

For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10^6,1\le k\le n-l$.

Subtask 1: For $20\%$ of the testdata, it is guaranteed that $n\le 1000$.

Subtask 2: For $10\%$ of the testdata, it is guaranteed that $l\le 5$.

Subtask 3: For $20\%$ of the testdata, it is guaranteed that $l\le 15$.

Subtask 4: No additional constraints.

Sample explanation $1$:

It is enough to remove the connection $(1,4)$.

Sample explanation $2$:

It is enough to remove the three connections $(8,14),(8,10),(8,16)$.

It can be proven that there is no way with fewer removals.

There may be other ways that also require removing only $3$ connections.

Translated by ChatGPT 5