If you talk about an even division in the usual sense of the words, it means dividing a thing equally. Today, you need to think about something different. A graph is to be divided into subgraphs with their numbers of nodes being even, that is, multiples of two.
You are given an undirected connected graph with even number of nodes. The given graph is to
be divided into its subgraphs so that all the subgraphs are connected and with even number of
nodes, until no further such division is possible. Figure I.1 illustrates an example. The original
graph of 8 nodes is divided into subgraphs with 4, 2, and 2 nodes. All of them have
To put it mathematically, an
Your task is to find an
The input consists of a single test case of the following format.
$n$ $m$ $x_1$ $y_1$ $\vdots$ $x_m$ $y_m$
The first line consists of two integers n and m. The first integer $n$ ($2 \leq n \leq 10^5$) is an even number representing the number of the nodes of the graph to be divided. The second integer $m$ ($n - 1 \leq m \leq 10^5$) is the number of the edges of the graph.
The nodes of the graph are numbered from $0$ to $n - 1$.
The subsequent m lines represent the edges of the graph. A line $x_i y_i$ ($0 \leq xi \lt yi \lt n$) means that there is an edge connecting the two nodes $x_i$ and $y_i$. There are no duplicated edges. The input graph is guaranteed to be connected.
If there exists an
If there are multiple even divisions, any of them are acceptable.
8 9 0 1 1 2 2 3 0 4 1 6 3 7 4 5 5 6 6 7
3 2 3 7 2 4 5 4 0 1 2 6
2 1 0 1
1 2 0 1
In the Sample 2, the singleton set of the set of the nodes of the original graph is already an even division.