Minimum Vertex Cover for Streetlights

You are given an undirected graph representing a network of streets. The graph consists of n intersections and m streets connecting these intersections. Each street is represented as an undirected edge connecting two intersections, and the graph is connected.

Your task is to determine a vertex cover of the graph using a greedy strategy. In other words, you need to choose a subset of intersections such that every street (edge) has at least one of its endpoints in the subset. This is analogous to placing streetlights at some intersections in order to illuminate all streets, and the goal is to minimize the number of streetlights used.

Note: Since finding the minimum vertex cover is NP‐hard, a greedy approximation approach is acceptable. In this problem, you are required to implement the following greedy algorithm:

Let E be the set of all edges in the graph.

• While there is an uncovered edge in E:
•  Pick an arbitrary uncovered edge (u, v).
•  Calculate the number of uncovered edges incident to u and to v.
•  Choose the vertex with the higher count. If both counts are equal, choose the one with the smaller index.
•  Add the chosen vertex to the vertex cover and mark all edges incident to that vertex as covered.

Finally, output the size of the vertex cover and the list of chosen vertices (in increasing order).

The algorithm should work correctly for the given test cases.

inputFormat

The first line contains two integers n and m — the number of intersections and the number of streets.

The next m lines each contain two integers u and v representing an undirected edge (a street) connecting intersections u and v.

You can assume that 1 ≤ u, v ≤ n and the graph is connected.

outputFormat

Output two lines. The first line contains a single integer k — the number of intersections chosen for the vertex cover. The second line contains k space-separated integers representing the indices of the chosen intersections in increasing order.

## sample

4 3
1 2
2 3
3 4

2
2 3

</p>