Voting#5489
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.
The first line contains two numbers, and , representing the number of vertices and edges in the graph, respectively (1 \leq N \leq 50000, 1 \leq M \leq 100000). The following lines each contain two numbers, and (1 \leq a, b \leq N, a \neq b), indicating a road between cities and .
The output should consist of two lines: the first line should contain the number of vertices , and the second line should list numbers from to .
Example 1
In the actual contest, the evaluation was conducted as follows:
You could download the input tests.
The output tests were evaluated, not the program itself.
If your selected vertices do not cover all edges, you will receive points for that test. If the answer is correct, the score depends on the size of the set you selected. Let your answer be , and the optimal be . Then you will earn 10 \cdot ((8b-7y)/b)^2 points (rounded to the nearest integer).
We decided to take the risk and evaluate your program at our own discretion.
