在本题中，我们将研究兔子的生活。

我们的兔子生活在林间空地中，其中一些空地由双向小径连接。没有小径会形成自环：每条小径都连接两个不同的空地。任意两片空地之间最多只有一条小径。

我们的兔子可以在地上挖洞，以便在发生危险时藏身。洞可以挖在每个空地的中心。为了让兔子藏进洞里，兔子只需要到达洞所在的空地，然后立即藏在那里。每个洞都可以容纳任意数量的兔子。

兔子宇宙有两个重要特征：任意两片空地之间都存在一条路径，且除了至多一片空地外，每片空地都与不超过两片其他空地相连。

兔子们想挖一些洞，以便在发生危险时，能够最小化所有兔子藏身所需的时间。请帮助它们找到合适的空地来挖洞。时间计算为兔子到达洞口所经过的小径数量。所有兔子都是独立移动和藏身的。

同时也假设兔子的数量足够多，以至于每片空地都至少有一只兔子。

输入格式

输入的第一行包含整数 $N$、$M$ 和 $K$：分别表示空地的数量、小径的数量以及要挖的洞的数量（$1 \le K \le N \le 1000$）。

接下来的 $M$ 行，每行描述一条小径，包含两个整数 $x_i$ 和 $y_i$：表示由这条小径连接的两片空地的编号（$1 \le x_i, y_i \le N$）。

输出格式

输出一个整数：在最优放置所有 $K$ 个洞的情况下，所有兔子藏身所需的最小可能时间。

样例

输入 1

5 6 1
3 1
3 2
3 4
3 5
1 2
4 5

输出 1

1

输入 2

8 8 2
1 2
2 3
3 4
4 1
1 5
5 6
6 7
7 8

输出 2

2