You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在遥远的银河系中，存在一个名为Zypher的星球。这个星球上居住着许多外星种族，它们之间有着复杂的关系。为了保护星球的和平与安全，Zypher星球的领袖希望组建一支强大的银河护卫队。

然而，不同种族之间并不总是和睦相处，有些种族之间可能是世仇。领袖需要根据种族间的仇敌关系，选择一些种族的代表组成护卫队，以确保任何两个入选的代表之间都不存在敌对关系。为了使护卫队更加强大，领袖希望选择尽可能多的代表加入队伍。

请编写一个程序，根据Zypher星球上种族间的仇敌关系，计算出最佳的护卫队组成方案。

输入格式

第一行包含两个正整数$n$和$m$，表示Zypher星球上有$n$个种族代表，代表间有$m$个仇敌关系。

接下来的$m$行中，每行包含两个正整数$u$和$v$，表示代表$u$与代表$v$是仇敌。

输出格式

第一行是护卫队的最大人数。

接下来一行是护卫队的组成情况，共$n$个数字，其中第$i$个数字$x_i$表示代表$i$是否在护卫队中，$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

数据范围与约定

• 对于 $30\%$ 数据：$n \le 20$，$m \le 100$。
• 对于所有数据：$n \le 100,m \le 3000$。