Description

Given a connected undirected graph with $N$ vertices and $M$ edges, find several simple cycles such that:

• These cycles do not share any edges.
• These cycles cover all vertices and edges.

A simple cycle is a cycle that does not pass through any vertex more than once.

It is guaranteed that the graph has no multiple edges, and that a solution exists.

Input Format

The first line contains two integers $N, M$, representing the number of vertices and the number of edges.
The next $M$ lines each contain two integers $u, v$, representing an edge.

Output Format

Output several lines. Each line contains several integers representing one simple cycle.

10 15
1 3
5 1
2 3
9 2
3 4
6 3
4 5
7 4
4 8
5 7
8 5
6 7
7 8
8 10
10 9

2 3 4 5 8 10 9
7 8 4
1 5 7 6 3

Hint

Sample Explanation

For Sample $1$:

Constraints

This problem uses bundled tests.

• Subtask 1 (38 pts): $N \le 2000$, $M \le 10^5$.
• Subtask 2 (17 pts): $N, M \le 10^5$.
• Subtask 3 (45 pts): No special constraints.

For $100\%$ of the testdata, $3 \le N, M \le 5 \times 10^5$.

This problem uses Special Judge.

Thanks to the SPJ provider

Notes

Translated from BalticOI 2014 Day2 C Senior Postmen。

Translated by ChatGPT 5