One Stroke, Every Street

Difficulty: 2000 6000 ms 128 MB

graphs euler-tour constructive

A snow plow must drive every street exactly once and return to its garage. The street network is a connected undirected graph in which every junction meets an even number of streets, so such a route always exists. Print one.

Input: the first line has N (junctions) and M (streets); each of the next M lines has an edge u v. There are no self-loops or duplicate streets, every vertex with any street has even degree, and all such vertices are connected.

Output: M+1 junction numbers separated by spaces: a closed walk that uses every street exactly once (start junction repeated at the end). Any valid route is accepted — a special judge checks your answer.

Constraints:

• 3 ≤ N ≤ 5×10⁴
• 3 ≤ M ≤ 1.2×10⁵

This problem is judged by a checker: your circuit does not have to match the sample output, it only has to be valid.

Sample Tests

3 3
1 2
2 3
1 3

1 3 2 1

5 6
1 2
2 3
3 1
3 4
4 5
5 3

1 3 5 4 3 2 1

Read the Editorial