描述

liouzhou_101住在柳侯公园附近,闲暇时刻都会去公园散散步。
很那啥的就是,柳侯公园的道路太凌乱了,假若不认识路就会走着走着绕回原来的那条路。
liouzhou_101就开始自己YY,假若给他当上那啥管理者,就会想尽量减少道路回圈的个数,但是大范围的改变道路终归不是什么良策。
经过调查,发现公园有N个景点,为了显示景点之间的优越性,我们按照1,2,…,N来把这N个景点编号,当然编号越小就说明越重要。
为了显示自己的英明决策,liouzhou_101决定,前K重要的景点最为重要,当然他们是标号为1…K了的。需要保证这K个景点不在任何一个环上,原因很简单,这前K个景点是很重要的景点,参观的人也很多,自然不会希望参观的人因为在兜圈子而迷路吧。
于是,我们所能够做的就是把之前建造好的一些道路清除掉,使得保证前K重要的景点不在任何一个环上。

输入格式

第一行包括三个正整数N,M和K,N表示景点的数量,M表示公园里的路径条数,K表示前K个景点最为重要。
再接下来M行,每行有两个正整数x和y,表示景点x和景点y之间有一条边。

输出格式

仅一行,输出至少去除多少条路径,使得前K个重要的景点不在任何一个环上。

样例输入

11 13 5
1 2
1 3
1 5
3 5
2 8
4 11
7 11
6 10
6 9
2 3
8 9
5 9
9 10

样例输出

3

数据范围与约定

我们的删边方案是,删除(2,3)(5,9)(3,5)这三条边,这样节点1到5都不在任何一个环上。
而且可知删除三条边已经是最少的了。

30%的数据,满足N≤10,M≤20;
60%的数据,满足N≤1,000,M≤10,000;
100%的数据,满足N≤100,000,M≤200,000。
注意:给出的无向图可能有重边和自环。