## Maximum Independent Set

View as PDF

Points: 15
Time limit: 2.0s
Memory limit: 128M

Problem type

Given a simple undirected graph with vertices numbered to and edges. -th edge is .

Calculate the maximum independent set.

The maximum independent set is the largest subset of nodes in the graph such that no nodes in the subset are connected by any edge in the original graph.

when

#### Input Specification

The first line contains two integers and .

The next lines each contain two integers: and , denoting an edge between and .

#### Output Specification

The first line contains an integer , the size of the largest independent set.

The next line contains integers, the nodes in an maximum independent set.

#### Sample Input

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

#### Sample Output

4
5 2 1 6