Vasya 演奏 FreeDiv。在这款游戏中,他管理着一个巨大的国家,该国家有 n 个城市,城市之间有 m 条双向道路。不幸的是,并不是每个城市都可以沿着这些道路到达任何其他城市。因此瓦夏决定将国家划分为多个省,以便在每个省中,每个城市都可以到达该省的所有城市,但省之间没有道路。
与其他回合制策略不同,在 FreeDiv 中,玩家有机会在城市之间建造隧道。这些隧道是双向道路,人们可以沿着隧道在不被敌人发现的情况下移动军队。然而,每个城市只能连接一条隧道。至于瓦夏(Vasya),他希望建立一个隧道网络,以便通过由道路和隧道组成的路径可以到达他所在州的任何一对城市。但此时每个省份连接的隧道不超过k条(否则万一其他省份被敌军占领,该省份将很难守住)。
Vasya发现,也许他无法针对国家目前的状况建立这样的网络。也许他得先在不同省份的城市之间修建几条道路,以合并各省份。您的任务是确定 Vasya 需要修建的最少道路数量,以便能够在最终状态下修建所需的隧道网络。
输入
第一行包含三个整数 n、m 和 k (1 ≤ n, k ≤ 106, 0 ≤ m ≤ 106)。接下来的 m 行每行包含两个整数。它们是由相应道路连接的城市的数量。没有道路将城市与其自身连接起来,并且每对城市之间最多只有一条道路。
输出
打印单个数字,附加道路的最小数量。
示例
输入 #1
3 3 2 1 2 2 3 3 1
输出 #1
0
输入 #2
4 2 2 1 2 3 4
输出 #2
0
输入 #3
4 0 2
输出 #3
1
注意
在第一个示例中,仅存在一个省份,因此无需修建任何隧道或道路。
在第二个示例中存在两个省。可以通过在城市 1 和 3 之间建造隧道来合并省份。
在第三个示例中,至少需要一条附加道路。例如,可以在城市 1 和 2 之间修建额外的道路,然后在城市 1 和 3、2 和 4 之间修建两条隧道。