#P1692. 部落卫队

部落卫队

题目描述

原始部落 byteland 中的居民们为了争夺有限的资源,经常发生冲突。几乎每个居民都有他的仇敌。部落酋长为了组织一支保卫部落的队伍,希望从部落的居民中选出最多的居民入伍,并保证队伍中任何 22 个人都不是仇敌。

给定 byteland 部落中居民间的仇敌关系,编程计算组成部落卫队的最佳方案。若有多种方案可行,输出字典序最大的方案。

输入格式

11 行有 22 个正整数 nnmm,表示 byteland 部落中有 nn 个居民,居民间有 mm 个仇敌关系。居民编号为 1,2,,n1,2, \cdots ,n。接下来的 mm 行中,每行有 22 个正整数 uuvv,表示居民 uu 与居民 vv 是仇敌。

输出格式

11 行是部落卫队的人数;文件的第 22 行是卫队组成 xix_i1in1 \le i \le nxi=0x_i=0 表示居民 ii 不在卫队中,xi=1x_i=1 表示居民 ii 在卫队中。

7  10
1  2
1  4
2  4
2  3
2  5
2  6
3  5
3  6
4  5
5  6
3
1 0 1 0 0 0 1

提示

对于 60%60\% 数据:n20n \le 20m100m \le 100

对于所有数据:n100,m3000n \le 100,m \le 3000。数据从所有合法数据从随机均匀取样。