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

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
import sys
from collections import defaultdict

class Graph(object):
	"""docstring for Graph"""
	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')
else:
	if 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")

class Graph(object):
	"""docstring for Graph"""
	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')
else:
	if len(ans) == (e+1) and ans[0] == ans[-1]:
# 		print(ans)
		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")