P6743 [BalticOI 2014] Senior Postmen (Day2)

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.

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 several lines. Each line contains several integers representing one simple cycle.

#### 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 @[tiger2005](https://www.luogu.com.cn/user/60864). #### Notes Translated from [BalticOI 2014 Day2 C Senior Postmen](https://boi.cses.fi/files/boi2014_day2.pdf)。 Translated by ChatGPT 5