Sebin Loves Euler Circuit
Time limit1sMemory limit256 MB
Given an undirected graph, add the fewest edges so the whole graph has an Euler circuit covering every edge exactly once, and print the added edges.
- Level
Medium7 of 10
- Topics
- Graph, Union-find, Greedy, Implementation
- Solved
- No attempts yet
Problem
An undirected graph with N vertices and M edges is given. The vertices are assigned N distinct natural numbers from 1 to N.
Sebin wants to add the minimum number of edges to the graph so that it has an Euler Circuit: one that visits all N vertices, uses every edge of the graph exactly once, and starts and ends at the same vertex.
Add the edges to the graph on Sebin's behalf!
Input
The first line contains the integers N and M, the number of vertices and the number of edges, separated by a space.
The next M lines contain the M edges.
The (i+1)-th line contains two integers Ai and Bi, the endpoints of the i-th edge, separated by a space (1 ≤ i ≤ M).
The i-th edge connects vertex Ai and vertex Bi (1 ≤ i ≤ M, 1 ≤ Ai ≤ N, 1 ≤ Bi ≤ N).
For all input data, 1 ≤ N ≤ 2×105 and N ≤ M ≤ 106.
Output
Print the minimum number of edges T that must be added on the first line.
On the next T lines, print the edges to add.
The (i+1)-th line contains the numbers of the two vertices connected by the i-th edge to add, separated by a space (1 ≤ i ≤ T).
If T = 0, you do not have to print the second line.