Road Network

After World War II, most of the roads connecting villages have been destroyed. The country has N villages, numbered from 1 to N, and M bidirectional roads, each connecting two different villages. There are no more than one road connecting the same pair of villages. These roads do not ensure the possibility of road connection between any two villages. There are groups of villages, where in each group any two villages are connected by roads. However, there is no road connection between villages belonging to different groups.

The government plans to reconstruct the road network and has the ability to build up to K new roads, each of which will connect two villages for which there is no road connection. After the construction of these new roads, if the design is correct, the number of village groups will decrease because more villages will be connected by roads. Find the minimum possible number of village groups that can remain after the construction of the new roads.

Problem

Develop a program in one of the IOI languages (Pascal, C, C++, Java) that reads the data and finds the minimum possible number of village groups remaining after the construction of the new roads.

Input Files

The input file named villages.in is a text file. The first line contains three integers N, M, K, separated in pairs by a single space: the number N of villages, the number M of existing roads, and the number K of new roads to be constructed. Each of the next M lines contains two integers A and B, separated by a single space, where 1 ~\le~ Α, Β ~\le~ N and Α ~\ne~ Β. This means that there is a bidirectional road connecting villages A and B.

Output Files

The output file named villages.out is a text file consisting of a single line containing a single integer: the minimum possible number of village groups remaining after the construction of the new roads.

Examples of Input - Output Files:

1st

STDIN (village.in)

7 2 2
1 2
6 5

STDOUT (villages.out)

3

Explanation: Initially, there are five groups of villages: {1, 2}, {3}, {4}, {5, 6}, and {7}. If two new roads are constructed, for example between villages (3, 7) and villages (3, 4), then only three groups will remain: {1, 2}, {3, 4, 7}, and {5, 6}. This is also the minimum number of groups that can result after the construction of two roads.

2nd

STDIN (village.in)

4 2 3
1 2
4 3

STDOUT (villages.out)

1

Explanation: In the second example, only one new road needs to be constructed to have only one group containing all villages.

3d

STDIN (village.in)

4 3 0
3 2
1 4
1 3

STDOUT (villages.out)

1

Explanation: In the third example, there is initially only one group of villages, and it will remain, even though the government cannot construct any roads (K=0).

Constraints:

• For test cases worth 50%, of the total points, it will be:
  1 ~\le~ Ν ~\le~ 10.000, 1 ~\le~ Μ ~\le~ 20.000, 0 ~\le~ Κ ~\le~ 10.000
• For test cases worth 100%, of the total points, it will be:
  1 ~\le~ Ν ~\le~ 1.000.000, 1 ~\le~ Μ ~\le~ 2.000.000, 0 ~\le~ Κ ~\le~ 1.000.000

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 2 sec.
Maximum available memory: 128 MB.