Finding Independent Set

题目描述

Given a simple undirected graph $G=(V,E)$. An independent set of $G$ is a set $S \subseteq V$ such that no two members of $S$ are connected by an edge in $E$ . Finding the maximum independent set of $G$ is an NP-hard problem. Here you are supposed to implement a greedy hueristic to find a near-maximum independent set. The algorithm works in the following way:

1. Collect any one un-visited vertex v into $S$ .
2. Delete all the vertices (and all the edges incident on them) that are adjacent to $v$ from $G$.
3. Repeat steps $1$ and $2$ until there is no un-visited vertex left in $G$.

In order to obtain the unique solution, when there are many options in step $1$, you must always choose the vertex with the smallest index.

输入格式

Each input file contains one test case. For each case, the first line contains $2$ positive integers: $n$ ($≤1000$), the number of vertices; and $m$, the number of edges. Then $m$ lines follow, each gives indices of the two ends of an edge. The vertices are indexed from $1$ to $n$.

输出格式

Print in a line the indices of the vertices in the independent set obtained by the given greedy algorithm. The indices must be in increasing order, and must be separated by exactly $1$ space. There must be no extra space at the beginning or the end of the line.

样例 #1

样例输入 #1

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

样例输出 #1

1 2 7 8