Voting

In Byteland, a vote is planned, and each person must travel to the nearest polling station to cast their vote. The residents of Byteland are quite lazy, so if the journey to the polling station takes more than one day, they will not participate. Byteland is depicted as an undirected graph, where traveling along each road takes exactly one day. People live along each road, evenly and densely. Polling stations can only be established at the vertices of the graph. To ensure everyone can vote, a polling station must be located at one of the two endpoints of each edge.

Your task is to assist the ruler in minimizing costs by selecting the smallest set of vertices where polling stations should be built.

Input

The first line contains two numbers, N and M, representing the number of vertices and edges in the graph, respectively (1 ≤ N ≤ 50000, 1 ≤ M ≤ 100000). The following M lines each contain two numbers, a and b (1 ≤ a, b ≤ N, a ≠ b), indicating a road between cities a and b.

Output

The output should consist of two lines: the first line should contain the number of vertices k, and the second line should list k numbers from 1 to N.

Examples

Note

In the actual contest, the evaluation was conducted as follows:

1. You could download the input tests.

2. The output tests were evaluated, not the program itself.

3. If your selected k vertices do not cover all M edges, you will receive 0 points for that test. If the answer is correct, the score depends on the size of the set you selected. Let your answer be y, and the optimal be b. Then you will earn 10·((8b-7y)/b)^2 points (rounded to the nearest integer).

We decided to take the risk and evaluate your program at our own discretion.