CF73D FreeDiv

Vasya 玩 FreeDiv 游戏。在这个游戏中，他管理着一个庞大的国家，这个国家有 $n$ 个城市和 $m$ 条双向道路连接这些城市。不幸的是，从某些城市无法通过这些道路到达其它任意城市。因此，Vasya 决定将国家划分为若干省份，使得每个省内，任意城市都可以到达该省内的所有城市，并且不同省份之间没有道路相连。 与其他回合制战略游戏不同，在 FreeDiv 中，玩家有机会在城市之间建造隧道。隧道是一种可以让军队悄无声息穿越的双向道路。然而，每个城市最多只能连接一条隧道。Vasya 希望建立一个隧道网络，使得国家中的任意一对城市都可以通过道路和隧道组合成的路径相互到达。但同时，每个省份连接的隧道数不超过 $k$ 条（否则，如果敌军占领其他省份，这个省份将难以防守）。 Vasya 发现，在当前情况下，他可能无法直接建立所需的隧道网络。也就是说，他可能首先需要在不同省份的城市之间修建几条新道路，将若干省份合并。你的任务是确定，为了能够建立满足上述要求的隧道网络，至少需要新修建多少条道路。

第一行包含三个整数 $n$、$m$ 和 $k$（$1\leq n, k \leq 10^{6}$，$0\leq m \leq 10^{6}$）。接下来的 $m$ 行，每行包含两个整数，表示一条连接两个城市的道路。没有道路连接同一个城市，本题中任意一对城市之间最多只有一条道路。

输出一个整数，表示至少需要新建的道路数。

在第一个样例中，只存在一个省份，因此不需要修建任何新的道路或隧道。 在第二个样例中，共有两个省份。可以通过在城市1和城市3之间修建一个隧道将两个省份合并。 在第三个样例中，至少需要新建一条道路。例如，可以在城市 $1$ 和城市 $2$ 之间新建一条道路，然后再分别在城市 $1$ 和城市 $3$、城市 $2$ 和城市 $4$ 之间建两条隧道。 由 ChatGPT 5 翻译