说明

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

给定 byteland 部落中居民间的仇敌关系，编程计算组成部落卫队的最佳方案。

输入格式

第 $1$ 行有 $2$ 个正整数 $n$ 和$m$，表示 byteland 部落中有$n$个居民，居民间有$m$个仇敌关系。(居民编号为 $1，2，…，n$)。

接下来的 $m$ 行中，每行有 $2$ 个正整数 $u$ 和 $v$，表示居民$u$与居民$v$是仇敌。

输出格式

第一行是部落卫队的最多人数；

第二行是卫队组成$x_{i}$,($1\leqslant i\leqslant n$),$x_{i}$=0表示居民i不在卫队中，$x_{i}$=1表示居民i在卫队中。

样例

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