#42 「 罪犯分组 」

统计

B城有一座监狱,一共关押着N名罪犯,编号分别为1-N。

他们的关系十分不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。

在详细考察了N名罪犯间的矛盾关系后,警察局长发现罪犯之间的矛盾关系可以用一个N个点M条边的无向图来表示:如果x到y有一条边,表示罪犯x和罪犯y有矛盾。

现在警察局长要把这些罪犯分成一些小组,每名罪犯属于且仅属于一个小组。

为了开展活动顺利,要求每个小组内最多有K对罪犯有矛盾,同时为了管理方便,警察局长希望最小化分成的小组数量。

那么,应如何分配罪犯,才能使分成的小组数量最少?这个最小值是多少?

输入格式

第一行3个整数,$N,M,K$,意义见上述。

接下来M行,每行两个数字$x$,$y$。表示x和y之间有矛盾。

输出格式

输出一行一个值,表示最少的分组数量。

样例数据

input

3 3 1
1 2
2 3
1 3

output

2

数据规模与约定

对于每个测试点,N分别等于2,4,6,8,10,12,14,15,16,16。

$0 \le M,K \le \frac{N(N-1)}{2}$

保证是一个无自环、无重边的无向图。

时间限制:1s

空间限制:512MB

Author: zrt