Problem: Harry Potter lost his Invisibility Cloak, running from the school caretaker Filch. Finding an invisible object is not an easy task. Fortunately, Harry has friends who are willing to help. Hermione Granger had read "The Invisibility Cloaks, and Everything about Them", as well as six volumes of "The Encyclopedia of Quick Search of Shortest Paths in Graphs, Network Flows, the Maximal Increasing Subsequences and Other Magical Objects". She has already developed a search algorithm for the invisibility cloak in complex dynamic systems (Hogwarts is one of them).

Hogwarts consists of n floors, numbered by integers from 1 to n. Some pairs of floors are connected by staircases. The staircases may change its position, moving exactly one end. Formally the situation is like this: if a staircase connects the floors a and b, then in one move it may modify its position so as to connect the floors a and c or b and c, where c is any floor different from a and b. Under no circumstances the staircase can connect a floor with itself. At the same time there can be multiple stairs between a pair of floors.

Initially, Harry is on the floor with the number 1. He does not remember on what floor he has lost the cloak and wants to look for it on each of the floors. Therefore, his goal is to visit each of n floors at least once. Harry can visit the floors in any order and finish the searching at any floor.

Nowadays the staircases move quite rarely. However, Ron and Hermione are willing to put a spell on any of them to help Harry find the cloak. To cause less suspicion, the three friends plan to move the staircases one by one, and no more than once for each staircase. In between shifting the staircases Harry will be able to move about the floors, reachable at the moment from the staircases, and look for his Invisibility Cloak. It is assumed that during all this time the staircases will not move spontaneously.

Help the three friends to compose a searching plan. If there are several variants to solve the problem, any valid option (not necessarily the optimal one) will be accepted.

Input

The first line contains integers n and m (1 ≤ n ≤ 100000, 0 ≤ m ≤ 200000), which are the number of floors and staircases in Hogwarts, respectively. The following m lines contain pairs of floors connected by staircases at the initial moment of time.

Output

In the first line print "YES" (without the quotes) if Harry is able to search all the floors, and "NO" otherwise. If the answer is positive, then print on the second line the number of staircases that Ron and Hermione will have to shift. Further output should look like this:

Harry's moves

a staircase's move

Harry's moves

a staircase's move

...

a staircase's move

Harry's moves

Each "Harry's move" should be represented as a list of floors in the order in which they have been visited. The total amount of elements of these lists must not exceed 106. When you print each list, first print the number of elements in it, and then in the same line print the actual space-separated elements. The first number in the first list should be the number 1 (the floor, from which Harry begins to search). Any list except the first one might contain the zero number of elements. Note that Harry can visit some floors again, but must visit all n floors at least once. Two consecutively visited floors must be directly connected by a staircase (at the time Harry goes from one of them to the other one). No two floors that are visited consequtively can be equal.

In the description of a "staircase's move" indicate the number of staircase (the staircases are numbered from 1 to m in the order in which they are given in the input data) and its new location (two numbers of the connected floors in any order).

Any staircase can be moved at most once. If there are several solutions, output any.

Examples

Input

6 4
1 2
1 3
2 3
4 5


Output

YES
2
3 1 2 3
2 3 5
3 5 4 5
4 5 6
3 6 5 3


Input

4 1
1 2


Output

NO


Input

5 5
1 2
1 3
3 4
3 5
4 5


Output

YES
0
6 1 2 1 3 4 5

Solution (in PYTHON):

Solution:
from collections import deque
def readarray(foo): return [foo(x) for x in raw_input().split()]


stairs = []
to = []
color = []
totalcolors = 0
deg = []
priority = []

extrastairs = []
extrastair = None


def doit():
	usedstairs = set()
	visited = set([0])
	stack = []
	res = []
	nextcolor = 1

	s = 0
	if extrastair is not None:
		(s, stair) = extrastair
		visited.add(s)
		usedstairs.add(stair)
		nextcolor += 1
		res.append([0])
		res.append([stair, 0, s])
	
	hasnextcolor = totalcolors > nextcolor
	layer = [s]
	stack.append([s, -1, -1, 0])

	while stack:
		(u, source, parent, start) = state = stack[-1]

		nexti = None
		nexts = None
		nextv = None
		for i in xrange(start, len(to[u])):
			s = to[u][i]
			if s == source: continue
			if s in usedstairs: continue
			(v1, v2) = stairs[s]
			v = v1 if v2 == u else v2
			if not hasnextcolor and v in visited: continue
			nexti = i
			nexts = s
			nextv = v
			break

		if nexti is None:
			if parent != -1:
				layer.append(parent)
			stack.pop()
			continue

		if nextv not in visited:
			visited.add(nextv)
			layer.append(nextv)
			state[3] = nexti
			stack.append([nextv, nexts, u, 0])
			continue
	
		usedstairs.add(nexts)
		nextv = priority[nextcolor]
		nextcolor += 1
		hasnextcolor = totalcolors > nextcolor

		res.append(layer)
		res.append([nexts, u, nextv])
		layer = [nextv]
		visited.add(nextv)
		
		state[3] = nexti + 1
		stack.append([nextv, nexts, u, 0])

	res.append(layer)
	return res if not hasnextcolor else None


def colorize(s, c):
	if color[s] != -1: return
	global totalcolors
	totalcolors += 1
	color[s] = c
	deg[c] = 1
	q = deque()
	q.append(s)
	source = {s : -1}
	while q:
		u = q.popleft()
		for stair in to[u]:
			if extrastair is not None and extrastair[1] == stair: continue
			(v1, v2) = stairs[stair]
			v = v1 if v2 == u else v2
			if color[v] != -1:
				if v != source[u]:
					extrastairs.append(stair)
				continue
			color[v] = c
			source[v] = u
			deg[c] += 1
			q.append(v)


def findextrastair():
	if extrastairs: return (stairs[extrastairs[0]][0], extrastairs[0])
	for u in xrange(len(to)):
		if len(to[u]) < 2: continue
		return (u, to[u][0])
	return None

def run():
	global to, color, deg, priority, extrastair, totalcolors
	n, m = readarray(int)
	to = [[] for i in xrange(n)]
	color = [-1] * n
	deg = [0] * n
	for i in xrange(m):
		u, v = sorted(readarray(lambda x: int(x) - 1))
		stairs.append((u, v))
		to[u].append(i)
		to[v].append(i)
	for i in xrange(n):
		colorize(i, i)

	if deg[0] == 1 and n > 1:
		extrastair = findextrastair()
		if extrastair is None:
			print "NO"
			return
		color = [-1] * n
		deg = [0] * n
		totalcolors = 0
		for i in xrange(n):
			colorize(i, i)
		deg[color[extrastair[0]]] = 100500
		
	
	deg[0] = 100500
	priority = sorted(range(n), lambda x, y: deg[y] - deg[x])[:totalcolors]
	res = doit()
	if res is None:
		print "NO"
		return

	print "YES"
	print len(res) / 2
	for i, line in enumerate(res):
		if i % 2 == 0:
			print len(line),
		print " ".join(map(lambda x: str(x + 1), line))

run()