Let G be a graph with a set of n nodes and a set of  m edges. A vertex cover VC is a subset of the nodes, such that each edge in graph G is covered by at least one node in the subset. (One or both ends of each edge must be in VC).

A minimal vertex cover is a vertex cover for G such that removing one of the nodes in the set causes at least one edge in G to be uncovered.

In this task, you are given a undirected graph as the input, and you have to find as small as possible vertex cover within the time limit. Your score is the average of ratios of the total number of nodes in vertex covers to the total nodes in the graph for all of the test cases.

Input

The first line contains two integers, n and m, representing the numbers of nodes and edges in the graph. 3  ≤ n ≤ 2000 and 3 ≤ m ≤ 40000. The nodes are numbered 1..n. The next m lines contain pair of integers representing edges between two nodes. The list of edges is not in any particular order.

Output

There should be only one line of output, listing all valid nodes in the vertex cover you found in the graph. The nodes are separated by one space.

Example

Input:
6 7
1 2
1 5
2 3
2 5
3 4
3 6
5 6

Output:
5 3 2