In Graph City, there are ~N~ buildings, numbered from ~1~ to ~N~. Water is currently distributed through a system of ~M~ pipes, with pipe ~i~ allowing water to flow in both directions between buildings ~u_i~ and ~v_i~. Unfortunately, water can only flow into a building if there are a series of pipes that form a path connecting it to the water pump, located at building ~1~. Due to poor city planning, the current arrangement of pipes may not allow all buildings to receive water. The city has hired you to help them solve this problem!

Thankfully, the city has recruited enough volunteers to help you move some of the existing pipes to new locations for free, however they are only willing to do this at most ~K~ times. Additional pipes can be built at any location at the cost of ~$1~. The city wants to know the minimum cost required to allow water to flow to all of the buildings.

Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

Subtask	Points	~N, M, K~
~1~	~10\%~	~1 \le N \le 100\,000~ ~0 \le M \le 200\,000~ ~K = M~
~2~	~15\%~	~1 \le N \le 100\,000~ ~0 \le M \le 200\,000~ ~K = 0~
~3~	~75\%~	~1 \le N \le 100\,000~ ~0 \le M \le 200\,000~ ~0 \le K \le M~

For all subtasks:

~1 \le u_i, v_i \le N~

~u_i \ne v_i~

There will be at most one pipe directly connecting any two buildings.

Input Specification

The first line contains 3 integers, ~N~, ~M~, and ~K~.

The next ~M~ lines describe the current arrangement of pipes in the city. Each line contains 2 integers, ~u_i~, ~v_i~, indicating a pipe allowing water to flow in both directions between buildings ~u_i~ to ~v_i~.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output a single integer, the minimum cost required to build new pipes to allow water to flow into all buildings, after moving at most ~K~ of the existing pipes.

Sample Input 1

4 6 6
1 2
3 4
4 2
3 1
4 1
3 2

Sample Output 1

0

Sample Explanation 1

Since all buildings are connected to the water pump, no new pipes are built or moved.

Sample Input 2

4 1 0
2 3

Sample Output 2

2

Sample Explanation 2

We can build a pipe between buildings ~1~ and ~2~, and another pipe between buildings ~3~ and ~4~ to connect all buildings to the water pump, for a total cost of ~$2~. The built pipes are coloured in green.

Sample Input 3

6 4 1
1 2
2 3
3 1
4 5

Sample Output 3

1

Sample Explanation 3

We can move the existing pipe between buildings ~2~ and ~3~ (red) to connect buildings ~1~ and ~4~ (blue) for free. We can then build a new pipe between buildings ~1~ and ~6~ (green), which costs ~$1~.