We are given a graph ~G~, and we want to split it in cycles, such that:

• In each cycle, each vertex is visited only once (except for the first vertex of the cycle).
• Each edge of the graph is in exactly one cycle.

The key observation to solve the problem is that a graph can be split in such cycles if and only if the degrees of all vertices are even. Knowing this, we can find any cycle in the graph, remove it from the graph (operation does not change the parity of degrees of vertices), save the cycle as an answer, and continue looking for cycles, while there are still edges left.

This can be implemented in ~\mathcal O(N+M)~ time with a modified depth-first traversal algorithm:

We spread from the initial vertex until we find a visited vertex, which means we found a cycle. We traverse back and remove edges of the cycle, and then we continue to look for cycles.

The only question we have left to answer is the following: how do we store edges?

Subtask 1

We store a boolean adjacency matrix.

Time and memory complexity: ~\mathcal O(N^2)~.

Subtask 2

We store adjacency lists and a set of pairs of integers, where we store removed edges.

Time complexity ~\mathcal O(M \log M)~, Memory complexity ~\mathcal O(N+M)~

Subtask 3

We store a list of edges ~e[0], e[1], \dots, e[M]~, and adjacency lists for each vertex, linking to the original list of edges. Now we can mark edges as removed in the original list of edges, thus checking if an edge is removed in ~\mathcal O(1)~.

Overall time and memory complexity: ~\mathcal O(N+M)~.