该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Given a simple undirected graph $G=(V, E)$ . Anindependent 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$ ( $\le 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.

题目示例数据

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

1 2 7 8