[POI2006]Zos

内存限制：259 MiB 时间限制：50 Sec

提交提交记录讨论

给出一个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，否则输出最大独立集的顶点个数。

样例输入

样例输出

最大独立集为{1, 3, 5, 6, 8}。

==================================
鸣谢Oimaster