Minimum Camera Placement for Road Surveillance

You are given a city represented as an undirected graph with \(n\) intersections and \(m\) roads. Each road connects two intersections. A camera installed at an intersection monitors all roads incident to that intersection. Your task is to determine the minimum number of cameras required to monitor every road in the city and to output one valid configuration of intersections where the cameras should be installed.

Problem Details:

• The city has \(n\) intersections numbered from 1 to \(n\).
• There are \(m\) roads; each road connects two different intersections.
• A road is considered monitored if at least one of its endpoints has a camera installed.
• If an intersection has no connecting roads, it does not require a camera.

Your solution should choose exactly one representative intersection from each connected component that contains at least one road. Note that if there are multiple valid solutions, any one of them is acceptable.

The mathematical formulation can be summarized as follows: Given a graph \(G = (V, E)\) where \(V\) is the set of intersections and \(E\) is the set of roads, find a set \(C \subseteq V\) such that for every edge \((u, v) \in E\), \(u \in C\) or \(v \in C\), and \(|C|\) is minimized.

inputFormat

The input is given via standard input and has the following format:

\(n\) \(m\)
\(u_1\) \(v_1\)
\(u_2\) \(v_2\)
... 
\(u_m\) \(v_m\)

Where:

• \(n\) is the number of intersections (\(1 \leq n \leq 10^5\)).
• \(m\) is the number of roads.
• Each of the next \(m\) lines contains two integers \(u_i\) and \(v_i\) representing a road between intersections \(u_i\) and \(v_i\).

outputFormat

Print a single line to standard output. The first number should be the minimum number of cameras required. If the number is greater than zero, follow it with a space-separated list of the intersections where the cameras should be installed.

For example, if the answer is 2 cameras placed at intersections 1 and 3, the output should be:

2 1 3

## sample

4 3
1 2
2 3
3 4

2 1 3