rt

题目描述：

有一个$n$个点$m$ 条边的图，你要进行下面两步操作

第一步：任意连$x$条边，得到一个新的图

第二步：在得到的新的图中任意连边，在这一步中，每个点最多连出去一条边，每个连通块至多连出去 $d$条边

你需要使得第二步结束后整个图连通，请问$x$最小是多少才能满足条件？

输入格式：

第一行两个整数，表示 $n，m ，d$

接下来 行每行两个整数表示一条边

输出格式：

输出一行一个整数，表示答案

样例输入 1

8 4 2
4 7
6 2 
6 5 
6 2

样例输出 2

1

样例输入2

10 4 2 
5 6
9 7
6 8
5 9

样例输出2

2

范围

对于$40$%的数据$n<10$

对于另外$30$% 的数据 $d=n$

对于$100$% 的数据，

$1<=n<=1e6,1<=m<=1e6$