A229. 部落卫队
编程题
普及/提高-
知识点
题目描述
原始部落 $byteland$ 中的居民们为了争夺有限的资源，经常发生冲突。几乎每个居民都有他的仇敌。部 落酋长为了组织一支保卫部落的队伍，希望从部落的居民中选出最多的居民入伍，并保证队伍中任何 $2$ 个 人都不是仇敌。
给定 $byteland$ 部落中居民间的仇敌关系，编程计算组成部落卫队的最佳方案。
给定 $byteland$ 部落中居民间的仇敌关系，编程计算组成部落卫队的最佳方案。
输入格式
第一行 $2$ 个正整数 $n$ 和 $m$，表示 $n$ 个人，$m$ 个仇敌关系，接下来 $m$ 行，每行 $2$ 个正整数 $u$ 和 $v$，表示 $u$ 和 $v$ 是仇敌（人编号 $1..n$）。
输出格式
第一行是最多的人数，第二行是队伍的组成 $X_i$，$0$ 表示第 $i$ 个人不入伍，$1$ 表示入伍。
输入输出样例
输入 #1
7 10 1 2 1 4 2 4 2 3 2 5 2 6 3 5 3 6 4 5 5 6
输出 #1
3 1 0 1 0 0 0 1
说明/提示
$1 \le n \le 1000, 1 \le m \le 10^4$