CF73D.FreeDiv

Vasya plays FreeDiv. In this game he manages a huge state, which has n cities and m two-way roads between them. Unfortunately, not from every city you can reach any other one moving along these roads. Therefore Vasya decided to divide the state into provinces so that in every province, one could reach from every city all the cities of the province, but there are no roads between provinces.

Unlike other turn-based strategies, in FreeDiv a player has the opportunity to build tunnels between cities. The tunnels are two-way roads along which one can move armies undetected by the enemy. However, no more than one tunnel can be connected to each city. As for Vasya, he wants to build a network of tunnels so that any pair of cities in his state were reachable by some path consisting of roads and a tunnels. But at that no more than k tunnels are connected to each province (otherwise, the province will be difficult to keep in case other provinces are captured by enemy armies).

Vasya discovered that maybe he will not be able to build such a network for the current condition of the state. Maybe he'll have first to build several roads between cities in different provinces to merge the provinces. Your task is to determine the minimum number of roads Vasya needs to build so that it was possible to build the required network of tunnels in the resulting state.

瓦西娅正在玩《FreeDiv》。在这款游戏中，他管理着一个庞大的国家，该国家包含 $n$ 座城市以及它们之间连接的 $m$ 条双向道路。遗憾的是，并非任意两座城市之间都可通过这些道路相互到达。因此，瓦西娅决定将整个国家划分为若干个“行省”，使得在每个行省内，任意两座城市均可通过该行省内部的道路相互到达，且不同行省之间不存在任何道路。

与其它回合制策略游戏不同，《FreeDiv》允许玩家在城市之间修建隧道。隧道是双向通道，军队可在其中移动而不被敌军察觉。然而，每座城市最多只能连接一条隧道。瓦西娅希望构建一个隧道网络，使得国家中任意两座城市之间都存在一条仅由道路和隧道组成的路径（即可达）。此外，每个行省内连接的隧道总数不得超过 $k$ 条（否则，若其他行省被敌军占领，该行省将难以防守）。

瓦西娅发现，在当前国家道路布局下，可能无法构建出满足上述要求的隧道网络。他或许需要先在不同行省之间的城市间修建若干条新道路，以合并部分行省。你的任务是：求出瓦西娅需修建的最少道路数量，使得在新增这些道路后，能够构建出满足要求的隧道网络。

The first line contains three integers n, m and k (1 ≤ n, k ≤ 106, 0 ≤ m ≤ 106). Each of the next m lines contains two integers. They are the numbers of cities connected by a corresponding road. No road connects city to itself and there is at most one road between each pair of cities.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 ≤ n, k ≤ 10^6$，$0 ≤ m ≤ 10^6$）。接下来的 $m$ 行每行包含两个整数，表示由对应道路连接的两座城市的编号。不存在连接同一座城市的道路，且任意两座城市之间至多只有一条道路。

Print a single number, the minimum number of additional roads.

输出一个整数，表示需要新增的最少道路数量。

In the first example only one province exists, so it is not necessary to build any tunnels or roads.

In the second example two provinces exist. It is possible to merge the provinces by building a tunnel between cities 1 and 3.

In the third example at least one additional road is necessary. For example it is possible to build additional road between cities 1 and 2 and build two tunnels between cities 1 and 3, 2 and 4 after that.

在第一个例子中，只存在一个省份，因此无需修建任何隧道或道路。

在第二个例子中，存在两个省份。可以通过在城市 1 和城市 3 之间修建一条隧道来合并这两个省份。

在第三个例子中，至少需要额外修建一条道路。例如，可以先在城市 1 和城市 2 之间修建一条额外的道路，然后在城市 1 和城市 3、城市 2 和城市 4 之间分别修建两条隧道。