The grand kingdom of Mancunia is famous for its tourist attractions and visitors flock to it throughout the year. King Mancunian is the benevolent ruler of the prosperous country whose main source of revenue is, of course, tourism.

The country can be represented by a network of unidirectional roads between the cities. But Mancunian, our benign monarch, has a headache. The road network of the country is not tourist-friendly and this is affecting revenue. To increase the GDP of the nation, he wants to redirect some of the roads to make the road network tourist-friendly and hence, ensure happiness and prosperity for his loyal subjects.

Now is the time for some formal definitions. :(

A road network is said to be tourist-friendly if for every city in the country, if a tourist starts his journey there, there is a path she can take to visit each and every city of the nation and traverse each road exactly once before ending up at the city where she started.

Given a description of the road network of Mancunia, can you come up with a scheme to redirect some (possibly none) of the roads to make it tourist-friendly?

-----Input-----
The first line contains two integers N and E denoting the number of cities and roads in the beautiful country of Mancunia respectively.
Each of the next E lines contains two integers a and b implying that there is a unidirectional road from city a to city b.

It is guaranteed that there aren't multiple roads in the exact same direction and that there is no road from a city to itself.

-----Output-----
If there is no solution, print "NO" (without quotes). Else, print "YES" (without quotes), followed by exactly E lines.
The ith line of output should represent the ith road in the input. It should have two integers a and b denoting that the final orientation of that road is from a to b.

-----Constraints-----

- 1 ≤ N ≤ 100000
- 1 ≤ E ≤ 200000
- 1 ≤ a, b ≤ N

Subtask 1: (20 points)
- 1 ≤ N ≤ 20
- 1 ≤ E ≤ 21

Subtask 2: (80 points)
- Same as original constraints

-----Example 1-----
Input:
3 3
1 2
2 3
3 1

Output:
YES
1 2
2 3
3 1

-----Example 2-----
Input:
3 2
1 2
2 3

Output:
NO

-----Example 3-----
Input:
5 6
1 2
2 3
3 4
2 4
2 5
1 5

Output:
YES
1 2
2 3
3 4
4 2
2 5
5 1

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Tree queries


Solutions:
ne = [int(k) for k in input().split()]
n = ne[0]
e = ne[1]
und_adjlist = []
und_nbrvert = []
for i in range(0, n):
	und_adjlist.append([])
	und_nbrvert.append(0)
i = 0
Edge = []
while i < e:
	edge = [int(x) for x in input().split()]
	Edge.append((edge[0], edge[1]))
	if i == 0:
		st = edge[0]
	p1 = edge[0]
	p2 = edge[1]
	und_adjlist[p1 - 1].append([p2, und_nbrvert[p2 - 1]])
	und_adjlist[p2 - 1].append([p1, und_nbrvert[p1 - 1]])
	und_nbrvert[p1 - 1] += 1
	und_nbrvert[p2 - 1] += 1
	i += 1
even_degree_graph = 1
for i in range(0, n):
	if und_nbrvert[i] % 2:
		even_degree_graph = 0
		break
	else:
		continue
if even_degree_graph:
	is_connected = []
	for i in range(0, n):
		is_connected.append(-1)

	def is_empty(stack):
		if stack == []:
			return 1
		else:
			return 0
	stack = ['a']
	circuit = []
	i = 0
	curr_loc = st
	is_connected[curr_loc - 1] = 1
	while not is_empty(stack):
		if i == 0:
			stack.pop()
		i += 1
		if not und_adjlist[curr_loc - 1] == []:
			adj = und_adjlist[curr_loc - 1].pop(-1)
			if not adj == []:
				und_nbrvert[curr_loc - 1] -= 1
				node = adj[0]
				is_connected[node - 1] = 1
				stack.append(curr_loc)
				prev_loc = curr_loc
				curr_loc = node
				und_adjlist[node - 1][adj[1]] = []
				und_nbrvert[node - 1] -= 1
		else:
			circuit.append(curr_loc)
			curr_loc = stack.pop()
	circuit.append(st)
	connected = 1
	for x in is_connected:
		if x != 1:
			connected = 0
			break
	if connected:
		print('YES')
		cir_len = len(circuit)
		order_circuit = set([])
		i = 0
		while i < cir_len - 1:
			order_circuit.add((circuit[i], circuit[i + 1]))
			i += 1
		i = 0
		while i < e:
			if Edge[i] in order_circuit:
				print(Edge[i][0], Edge[i][1])
			else:
				print(Edge[i][1], Edge[i][0])
			i += 1
	else:
		print('NO')
else:
	print('NO')


def main():
	from sys import stdin, stdout
	import collections
	(n, m) = map(int, stdin.readline().split())
	adj = collections.defaultdict(list)
	tmpstack = collections.deque()
	resstack = collections.deque()
	visited = [False for x in range(n)]
	en = [0 for x in range(n)]
	inputlist = []
	opset = set()
	for i in range(m):
		(a, b) = map(int, stdin.readline().split())
		inputlist.append((a, b))
		en[a - 1] += 1
		en[b - 1] += 1
		adj[a - 1].append(b - 1)
		adj[b - 1].append(a - 1)
	for i in en:
		if i & 1:
			flag = False
			break
		else:
			flag = True
	if flag:
		tmpstack.append(0)
		tmpstack.appendleft(adj[0][0])
		p = adj[0][0]
		adj[0].remove(p)
		adj[p].remove(0)
		while tmpstack[0]:
			top = tmpstack[0]
			k = adj[top][0]
			tmpstack.appendleft(k)
			adj[top].remove(k)
			adj[k].remove(top)
		while len(tmpstack):
			top = tmpstack[0]
			if len(adj[top]):
				k = adj[top][0]
				tmpstack.appendleft(k)
				adj[top].remove(k)
				adj[k].remove(top)
			else:
				resstack.appendleft(tmpstack.popleft())
				visited[resstack[0]] = True
		for i in range(len(resstack) - 1):
			opset.add((resstack[i] + 1, resstack[i + 1] + 1))
		if all(visited):
			stdout.write('YES\n')
			for i in range(len(inputlist)):
				if inputlist[i] in opset:
					stdout.write(str(inputlist[i][0]) + ' ' + str(inputlist[i][1]) + '\n')
				else:
					stdout.write(str(inputlist[i][1]) + ' ' + str(inputlist[i][0]) + '\n')
		else:
			stdout.write('NO\n')
	else:
		stdout.write('NO\n')
main()


class Graph(object):

	def __init__(self, vertices):
		self.vertices = vertices
		graph = dict()
		for i in range(1, vertices + 1):
			graph[i] = []
		self.graph = graph

	def add_edge(self, a, b):
		self.graph[a].append(b)
		self.graph[b].append(a)

	def eulerPath(self):
		g = self.graph
		odd = [k for (k, v) in g.items() if len(v) % 2 == 1]
		if len(odd) == 0:
			odd = [list(g.keys())[0]]
		elif len(odd) == 1 or len(odd) > 2:
			return None
		path = []
		stack = [odd[-1]]
		while stack:
			u = stack[-1]
			if g[u]:
				v = g[u][0]
				del g[u][0]
				del g[v][g[v].index(u)]
				stack.append(v)
			else:
				path.append(stack.pop())
		return path
(n, e) = map(int, input().strip().split())
g = Graph(n)
u = []
v = []
for i in range(e):
	(a, b) = map(int, input().strip().split())
	g.add_edge(a, b)
	u.append(a)
	v.append(b)
ans = g.eulerPath()
if ans is None:
	print('NO')
elif len(ans) == e + 1 and ans[0] == ans[-1]:
	print('YES')
	temp_dict = {}
	for i in range(len(ans) - 1, 0, -1):
		if ans[i] in temp_dict:
			temp_dict[ans[i]][ans[i - 1]] = True
		else:
			temp_dict[ans[i]] = {ans[i - 1]: True}
	for i in range(e):
		if u[i] in temp_dict and v[i] in temp_dict[u[i]]:
			print(u[i], v[i])
		else:
			print(v[i], u[i])
else:
	print('NO')


def EulerianCycle(G, G_rev, edges):
	if len(G) > 1:
		start = 1
	path = []
	while start:
		u = None
		while u != start:
			if u is None:
				u = start
			path.append(u)
			if len(G[u]) == 0 and len(G_rev[u]) == 0:
				return None
			if len(G[u]) == 0:
				(v, i) = G_rev[u].pop(0)
				G_rev[v].append((u, i))
				G[u].append((v, i))
				G[v].remove((u, i))
			(v, i) = G[u].pop(0)
			G_rev[v].remove((u, i))
			edges[i] = (u, v)
			u = v
		start = None
		for (idx, u) in enumerate(path):
			if len(G[u]) > 0 or len(G_rev[u]) > 0:
				start = u
				break
	if len(path) > 0:
		path.append(path[0])
		return path
	else:
		return None

def DeBruijnGraph(N, edges):
	(G, G_rev) = ([], [])
	for _ in range(N + 1):
		G.append([])
		G_rev.append([])
	for (i, (u, v)) in enumerate(edges):
		G[u].append((v, i))
		G_rev[v].append((u, i))
	return (G, G_rev)

def check(N, E, edges):
	trip = []
	if N > E:
		return ('NO', trip)
	(G, G_rev) = DeBruijnGraph(N, edges)
	path = EulerianCycle(G, G_rev, edges)
	if path is not None and len(path) == E + 1:
		trip = []
		for (u, v) in edges:
			trip.append(str(u) + ' ' + str(v))
		return ('YES', trip)
	else:
		return ('NO', trip)
(N, E) = tuple(map(int, input().strip().split()))
edges = [tuple(map(int, input().strip().split())) for _ in range(E)]
(result, trip) = check(N, E, edges)
print(result)
if 'YES' == result:
	print('\n'.join(trip))


import sys
from collections import defaultdict

class Graph(object):

	def __init__(self, vertices):
		self.vertices = vertices
		self.graph = defaultdict(list)

	def add_edge(self, a, b):
		self.graph[a].append(b)
		self.graph[b].append(a)

	def eulerPath(self):
		g = self.graph
		odd = [k for (k, v) in g.items() if len(v) % 2 == 1]
		if len(odd) == 0:
			odd = [list(g.keys())[0]]
		elif len(odd) == 1 or len(odd) > 2:
			return None
		path = []
		stack = [odd[-1]]
		while stack:
			u = stack[-1]
			if g[u]:
				v = g[u][0]
				del g[u][0]
				del g[v][g[v].index(u)]
				stack.append(v)
			else:
				path.append(stack.pop())
		return path
(n, e) = map(int, sys.stdin.readline().strip().split())
g = Graph(n)
u = []
v = []
for i in range(e):
	(a, b) = map(int, sys.stdin.readline().strip().split())
	g.add_edge(a, b)
	u.append(a)
	v.append(b)
ans = g.eulerPath()
if ans is None:
	print('NO')
elif len(ans) == e + 1 and ans[0] == ans[-1]:
	print('YES')
	temp = defaultdict(defaultdict)
	for i in range(len(ans) - 1, 0, -1):
		temp[ans[i]][ans[i - 1]] = True
	for i in range(e):
		if u[i] in temp and v[i] in temp[u[i]]:
			print(u[i], v[i])
		else:
			print(v[i], u[i])
else:
	print('NO')