[POI2006]Zos

时间限制:50s      空间限制:259MB

题目描述

给出一个N个点M条边的无向图G,定义图G的一个独立集为一个顶点集合V’,满足V’∈V,并且对于任何a∈V’且b∈V’的a和b,不存在(a,b)∈E。 问是否存在顶点个数不小于K的独立集,如果存在,找出顶点个数最多的独立集。


输入格式

第一行两个正整数N (2 <= N <= 1,000,000)、K (N-10 <= K <= N)。第二行一个正整数M (1 <= M <= 3,000,000)。接着M行,每行两个正整数a和b (1 <= a, b <= N, a ≠ b),表示一条边。(注意同样的边可能多次出现)


输出格式

如果不存在顶点个数不小于K的独立集,就输出NIE,否则输出最大独立集的顶点个数。


样例输入

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

样例输出

5

提示

最大独立集为{1, 3, 5, 6, 8}。 ================================== 鸣谢Oimaster


题目来源

没有写明来源