Read problems statements [Hindi] , [Vietnamese] , [Mandarin Chinese] , [Russian] and [Bengali] as well.

You are given a directed acyclic graph with $N$ vertices (numbered $1$ through $N$) and $M$ edges. You want to destroy it all! To destroy the graph, you should delete all of its vertices. 

In one step, you are allowed to delete at most two vertices; you may only delete a vertex when there is no edge from it to another (not yet deleted) vertex. You may not delete two vertices when there is an edge between them either.

Find a way to destroy the graph in the minimum number of steps.

------  Input ------
The first line of the input contains two space-separated integers $N$ and $M$.
Each of the next $M$ lines contains two space-separated integers $U$ and $V$ denoting an edge from vertex $U$ to vertex $V$.

------  Output ------
The first line of the output should contain a single integer $S$ denoting the minimum number of steps needed to destroy the graph.
Each of the next $S$ lines should describe one step; it should contain an integer $K$ ($1 ≤ K ≤ 2$), followed by a space and $K$ space-separated integers denoting the numbers of vertices deleted in this step.

------  Constraints  ------
$1 ≤ N, M ≤ 10^{6}$
the graph on the input does not contain any cycles or self-loops

------  Scoring ------
The score for each test file is $10 \cdot (C/S)^2$, where $C$ is the number of steps in which you deleted exactly $2$ vertices. The final score of your submission is equal to the sum of scores for each test file.

There are twenty test cases. During the contest, the displayed score will account for exactly four test files, i.e. your score reflects your submission's performance on 20% (4/20) of the test files. However, if your program gets a non-AC verdict on any test file, your submission's verdict will be non-AC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to include the sum of your program's scores over the other sixteen test files.

------  Example Input ------

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

------  Example Output ------

4
2 4 5
2 6 3
1 2
1 1

Source: codechef | Difficulty: VERY_HARD


Solutions:
(n, m) = map(int, input().split())
ind = [[] for i in range(n)]
out = [0] * n
for i in range(m):
	e = list(map(int, input().split()))
	e[0] = e[0] - 1
	e[1] = e[1] - 1
	out[e[0]] += 1
	ind[e[1]].append(e)
q = []
for i in range(n):
	if out[i] == 0:
		q.append(i)
ans = []
while q:
	a = q.pop(0)
	a1 = ind[a]
	if q:
		b = q.pop(0)
		b1 = ind[b]
		for elem in b1:
			out[elem[0]] = out[elem[0]] - 1
		for elem in b1:
			if out[elem[0]] == 0:
				q.append(elem[0])
		ans.append([2, a + 1, b + 1])
	else:
		ans.append([1, a + 1])
	for elem in a1:
		out[elem[0]] -= 1
	for elem in a1:
		if out[elem[0]] == 0:
			q.append(elem[0])
print(len(ans))
for i in ans:
	print(*i)


(n, m) = map(int, input().strip().split())
gr = [[] for i in range(n + 1)]
for i in range(m):
	(x, y) = map(int, input().strip().split())
	gr[x].append(y)
inorder = [0] * (n + 1)
for i in gr:
	for j in i:
		inorder[j] += 1
que = []
for i in range(1, n + 1):
	if inorder[i] == 0:
		que.append(i)
top = []
while que:
	u = que.pop(0)
	top.append(u)
	for v in gr[u]:
		inorder[v] -= 1
		if inorder[v] == 0:
			que.append(v)
top = top[::-1]
p = []
i = 0
while i < n:
	if i + 1 < n and (top[i] not in gr[top[i + 1]] and top[i + 1] not in gr[top[i]]):
		p.append([2, top[i], top[i + 1]])
		i += 2
	else:
		p.append([1, top[i]])
		i += 1
print(len(p))
for i in range(len(p)):
	print(*p[i])


from heapq import *

def input_tc():
	(num_nodes, num_edges) = [int(x) for x in input().split()]
	edges = [list() for _ in range(num_nodes + 1)]
	for _ in range(num_edges):
		(a, b) = [int(x) for x in input().split()]
		edges[a].append(b)
	return (num_nodes, num_edges, edges)

def get_reversed_edges(edges):
	redges = [list() for _ in edges]
	for a in range(1, len(edges)):
		for b in edges[a]:
			redges[b].append(a)
	return redges

def calc_depths(edges, redges):
	depths = [-1] * len(edges)
	refcounts = [len(x) for x in redges]
	todo = [i for i in range(1, len(edges)) if not refcounts[i]]
	d = 1
	while todo:
		todo2 = list()
		for node in todo:
			refcounts[node] -= 1
			if refcounts[node] < 1:
				refcounts[node]
				depths[node] = d
				for child in edges[node]:
					todo2.append(child)
		todo = todo2
		d += 1
	return depths

def solve(num_nodes, num_edges, edges):
	redges = get_reversed_edges(edges)
	depths = calc_depths(edges, redges)
	childcounts = [len(edges[i]) for i in range(len(edges))]
	todo = [(0 - depths[i], i) for i in range(1, len(edges)) if childcounts[i] == 0]
	heapify(todo)
	answer = []
	while todo:
		nodes = [heappop(todo)[1]]
		if todo:
			nodes.append(heappop(todo)[1])
		answer.append((len(nodes),) + tuple(nodes))
		for node in nodes:
			for parent in redges[node]:
				childcounts[parent] -= 1
				if childcounts[parent] < 1:
					heappush(todo, (0 - depths[parent], parent))
	return answer
tc = input_tc()
ans = solve(*tc)
print(len(ans))
for x in ans:
	print(*x)


import itertools
[n, m] = list(map(int, input().split()))
adjout = {}
adjin = {}
l = []
ol = {}
p = []
for i in range(1, n + 1):
	adjout[i] = []
	adjin[i] = []
	ol[i] = 0
for j in range(m):
	[u, v] = list(map(int, input().split()))
	adjout[u].append(v)
	adjin[v].append(u)
	ol[u] += 1
for (key, value) in ol.items():
	if value == 0:
		l.append(key)
while len(l) != 0:
	if len(l) == 1:
		p.append([1, l[0]])
		data3 = l[0]
		for key in list(adjin[data3]):
			ol[key] -= 1
			if ol[key] == 0:
				l.append(key)
		l.remove(data3)
	else:
		p.append([2, l[0], l[1]])
		data1 = l[0]
		data2 = l[1]
		l.remove(data1)
		l.remove(data2)
		for ii in [data1, data2]:
			for key in list(adjin[ii]):
				ol[key] -= 1
				if ol[key] == 0:
					l.append(key)
print(len(p))
for jj in p:
	for kk in jj:
		print(kk, end=' ')
	print()


from bisect import insort, bisect_left
from collections import defaultdict

def edge(u, v):
	counter[u] += 1
	rgraph[v].append(u)
	graph[u].append(v)
(n, m) = map(int, input().split())
rgraph = defaultdict(list)
graph = defaultdict(list)
counter = [0] * (n + 1)
present = [-1] * (n + 1)
weight = [0] * (n + 1)
pmt = [[1] * 5 for x in range(n + 1)]
for i in range(m):
	(u, v) = map(int, input().split())
	edge(u, v)
	present[u] = 0
	weight[v] += 1
	pmt[v][4] = 1 / weight[v]
for i in rgraph:
	for j in rgraph[i]:
		xc = counter[j]
		if xc <= 4:
			pmt[i][xc - 1] += 1
dlt = list()
for i in range(1, n + 1):
	if present[i] == -1:
		insort(dlt, [[pmt[i][4], 1 / pmt[i][0], 1 / pmt[i][1], 1 / pmt[i][2], 1 / pmt[i][3]], i])
		present[i] = 1
stp = 0
cp = n
ans = [[0] * 3 for x in range(n)]
while cp > 0:
	ct = 0
	stp += 1
	tmp = [0] * 2
	dl = list()
	while dlt != [] and ct < 2:
		q = dlt[0]
		i = q[1]
		present[i] = 0
		dlt.pop(0)
		ct += 1
		cp -= 1
		if i in rgraph:
			for j in rgraph[i]:
				counter[j] -= 1
				xc = counter[j]
				if 0 < xc <= 4:
					for k in graph[j]:
						if present[k] == 1:
							dlt.pop(bisect_left(dlt, [[pmt[k][4], 1 / pmt[k][0], 1 / pmt[k][1], 1 / pmt[k][2], 1 / pmt[k][3]], k]))
						if xc <= 3:
							pmt[k][xc - 1] += 1
							pmt[k][xc] -= 1
						else:
							pmt[k][3] += 1
						if present[k] == 1:
							insort(dlt, [[pmt[k][4], 1 / pmt[k][0], 1 / pmt[k][1], 1 / pmt[k][2], 1 / pmt[k][3]], k])
				if counter[j] == 0:
					dl.append(j)
		tmp[ct - 1] = i
	ans[stp - 1][0] = ct
	ans[stp - 1][1] = tmp[0]
	if ct == 2:
		ans[stp - 1][2] = tmp[1]
	for q in dl:
		insort(dlt, [[pmt[q][4], 1 / pmt[q][0], 1 / pmt[q][1], 1 / pmt[q][2], 1 / pmt[q][3]], q])
		present[q] == 1
print(stp)
for i in range(stp):
	if ans[i][0] == 2:
		print(2, ans[i][1], ans[i][2])
	else:
		print(1, ans[i][1])


import queue
[n, m] = list(map(int, input().split()))
adjlist = {}
adjlist2 = {}
outlist = {}
step = 0
res = []
l = queue.Queue(maxsize=n)
for i in range(1, n + 1):
	adjlist[i] = []
	adjlist2[i] = []
	outlist[i] = 0
while m:
	[u, v] = list(map(int, input().split()))
	adjlist[u].append(v)
	adjlist2[v].append(u)
	outlist[u] += 1
	m -= 1
for (key, value) in outlist.items():
	if value == 0:
		l.put(key)
while l.empty() != True:
	if l.qsize() == 1:
		step += 1
		data = l.get()
		res.append([1, data])
		for key in list(adjlist2[data]):
			outlist[key] -= 1
			if outlist[key] == 0:
				l.put(key)
			adjlist[key].remove(data)
	else:
		step += 1
		data1 = l.get()
		data2 = l.get()
		res.append([2, data1, data2])
		for data in [data1, data2]:
			for key in adjlist2[data]:
				outlist[key] -= 1
				if outlist[key] == 0:
					l.put(key)
				adjlist[key].remove(data)
print(step)
for i in res:
	print(*i)


(n, m) = map(int, input().split())
child = {}
l = {}
for i in range(m):
	(a, b) = map(int, input().split())
	if a not in child:
		child[a] = 1
	else:
		child[a] += 1
	if b not in l:
		l[b] = [a]
	else:
		l[b].append(a)
mainans = []
startans = []
for i in l:
	if i not in child:
		startans.append(i)
mainans.append(startans)
expnodes = []
for i in range(1, n + 1):
	if i not in l and i not in child:
		expnodes.append(i)
parcount = {}
for count in range(1000000):
	levansc = []
	for i in mainans[count]:
		if i in l:
			for j in l[i]:
				if j not in parcount:
					parcount[j] = child[j] - 1
				else:
					parcount[j] -= 1
				if parcount[j] == 0:
					levansc.append(j)
	if len(levansc) == 0:
		break
	mainans.append(levansc)
	count += 1
ans = []
count = 0
prev = 0
bt = 0
for i in mainans:
	j = 0
	while j < len(i):
		new = i[j]
		if count % 2 == 1:
			if i[j] in child:
				if child[i[j]] == 0:
					ans.append(i[j])
					ans.insert(-2, '2')
					bt += 1
					count = 0
					if i[j] in l:
						for a in l[i[j]]:
							child[a] -= 1
					if prev in l:
						for b in l[prev]:
							child[b] -= 1
				elif len(expnodes) != 0:
					w = expnodes.pop()
					ans.append(w)
					ans.insert(-2, '2')
					bt += 1
					for b in l[prev]:
						child[b] -= 1
					ans.append(i[j])
					count = 1
					prev = i[j]
				else:
					ans.insert(-1, '1')
					bt += 1
					for b in l[prev]:
						child[b] -= 1
					ans.append(i[j])
					count = 1
					prev = i[j]
			else:
				ans.append(i[j])
				ans.insert(-2, '2')
				bt += 1
				count = 0
				for a in l[i[j]]:
					child[a] -= 1
				for b in l[prev]:
					child[b] -= 1
		else:
			ans.append(i[j])
			prev = i[j]
			count = 1
		j += 1
if count == 1:
	if len(expnodes) != 0:
		w = expnodes.pop()
		ans.append(w)
		ans.insert(-2, '2')
		count = 0
		bt += 1
		while len(expnodes) > 0:
			if count == 1:
				w = expnodes.pop()
				ans.append(w)
				ans.insert(-2, '2')
				bt += 1
				count = 0
			else:
				w = expnodes.pop()
				ans.append(w)
				count = 1
		if count == 1:
			ans.insert(-1, '1')
			bt += 1
	else:
		ans.insert(-1, '1')
		bt += 1
else:
	while len(expnodes) > 0:
		if count == 1:
			w = expnodes.pop()
			ans.append(w)
			ans.insert(-2, '2')
			bt += 1
			count = 0
		else:
			w = expnodes.pop()
			ans.append(w)
			count = 1
	if count == 1:
		ans.insert(-1, '1')
		bt += 1
print(bt)
s = ''
i = 0
while i < len(ans):
	if ans[i] == '1':
		print(ans[i], ans[i + 1])
		i = i + 2
	else:
		print(ans[i], ans[i + 1], ans[i + 2])
		i = i + 3


import bisect

def edge(u, v):
	counter[u] += 1
	ccounter[u] += 1
	if weight[v] != 10 ** (-5):
		rgraph[v].append(u)
	else:
		rgraph[v] = [u]
	if counter[u] != 1:
		graph[u].append(v)
	else:
		graph[u] = [v]
(n, m) = map(int, input().split())
rgraph = dict()
graph = dict()
counter = [0] * (n + 1)
ccounter = [0] * (n + 1)
present = [-1] * (n + 1)
weight = [10 ** (-5)] * (n + 1)
for i in range(m):
	(u, v) = map(int, input().split())
	edge(u, v)
	present[u] = 0
	weight[v] += 1
total = [0] * (n + 1)
for i in rgraph:
	for j in rgraph[i]:
		total[i] += counter[j]
cdlt = list()
for i in range(1, n + 1):
	if present[i] == -1:
		bisect.insort(cdlt, [total[i] / weight[i], i])
		present[i] = 1
stp = 0
cp = n
ans = [[0] * 3 for x in range(n)]
while cp > 0:
	ct = 0
	stp += 1
	tmp = [0] * 2
	dl = list()
	while cdlt != [] and ct < 2:
		q = cdlt[0]
		cdlt.pop(0)
		i = q[1]
		present[i] = 0
		ct += 1
		cp -= 1
		if i in rgraph:
			for j in rgraph[i]:
				counter[j] -= 1
				for k in graph[j]:
					if present[k] == 1:
						cdlt.pop(bisect.bisect_left(cdlt, [total[k] / weight[k], k]))
						total[k] -= 1
						bisect.insort(cdlt, [total[k] / weight[k], k])
					else:
						total[k] -= 1
				if counter[j] == 0:
					dl.append(j)
		tmp[ct - 1] = i
	ans[stp - 1][0] = ct
	ans[stp - 1][1] = tmp[0]
	if ct == 2:
		ans[stp - 1][2] = tmp[1]
	for j in dl:
		bisect.insort(cdlt, [total[j] / weight[j], j])
		present[j] = 1
print(stp)
for i in range(stp):
	if ans[i][0] == 2:
		print(2, ans[i][1], ans[i][2])
	else:
		print(1, ans[i][1])


from collections import defaultdict
(n, m) = map(int, input().strip().split())
g = {}
for i in range(1, n + 1):
	g[i] = [[], 0, []]
for i in range(m):
	(u, v) = map(int, input().strip().split())
	g[u][0].append(v)
	g[u][1] += 1
	g[v][2].append(u)
prt = list()
(ln, ms) = (0, 0)
que = list()
for i in range(1, n + 1):
	if g[i][1] == 0:
		que.append(i)
		ln += 1
while ln > 0:
	if ln > 1:
		ln -= 2
		(a, b) = (que.pop(0), que.pop(0))
		prt.append([2, a, b])
		ms += 1
		for el in g[a][2]:
			g[el][1] -= 1
			if g[el][1] == 0:
				que.append(el)
				ln += 1
		for el in g[b][2]:
			g[el][1] -= 1
			if g[el][1] == 0:
				que.append(el)
				ln += 1
	else:
		ln -= 1
		a = que.pop(0)
		prt.append([1, a])
		ms += 1
		for el in g[a][2]:
			g[el][1] -= 1
			if g[el][1] == 0:
				que.append(el)
				ln += 1
print(ms)
for i in range(ms - 1):
	for el in prt[i]:
		print(el, end=' ')
	print()
for el in prt[-1]:
	print(el, end=' ')


k = [int(j) for j in input().split()]
a = [[0] * k[0]] * k[0]
outg1 = [0] * k[0]
inc = [0] * k[0]
outge = {}
inco = {}
for j in range(k[1]):
	b = [int(k) for k in input().split()]
	a[b[0] - 1][b[1] - 1] = 1
	outg1[b[0] - 1] = outg1[b[0] - 1] + 1
	inc[b[1] - 1] = inc[b[1] - 1] + 1
	if b[0] - 1 in outge.keys():
		outge[b[0] - 1].append(b[1] - 1)
	else:
		outge[b[0] - 1] = [b[1] - 1]
	if b[1] - 1 in inco.keys():
		inco[b[1] - 1].append(b[0] - 1)
	else:
		inco[b[1] - 1] = [b[0] - 1]
curr = []
ans = []
for i in range(k[0]):
	if outg1[i] == 0:
		curr.append(i)
while len(curr) > 0:
	if len(curr) >= 2:
		ans.append([curr[0], curr[1]])
		if curr[0] in inco.keys():
			for i in inco[curr[0]]:
				outg1[i] = outg1[i] - 1
				if outg1[i] == 0:
					curr.append(i)
		if curr[1] in inco.keys():
			for i in inco[curr[1]]:
				outg1[i] = outg1[i] - 1
				if outg1[i] == 0:
					curr.append(i)
		curr.pop(0)
		curr.pop(0)
	elif len(curr) == 1:
		ans.append([curr[0]])
		if curr[0] in inco.keys():
			for i in inco[curr[0]]:
				outg1[i] -= 1
				if outg1[i] == 0:
					curr.append(i)
		curr.pop(0)
print(len(ans))
temp = 0
for i in ans:
	if len(ans[0]) == 2 and len(ans[1]) == 1 and (i == ans[0] or i == ans[1]) and (outg1[ans[1][0]] == 0):
		if i == ans[0]:
			print('1 ' + str(ans[1][0] + 1))
		elif i == ans[1]:
			print('2 ' + str(ans[0][0] + 1) + ' ' + str(ans[0][1] + 1))
	elif len(i) == 2:
		print('2 ' + str(i[0] + 1) + ' ' + str(i[1] + 1))
	elif len(i) == 1:
		print('1 ' + str(i[0] + 1))


class MaxHeap:

	def __init__(self):
		self.arr = [0]
		self.heap_size = 0

	def parent(self, i):
		return (i - 1) // 2

	def left(self, i):
		return 2 * i + 1

	def right(self, i):
		return 2 * i + 2

	def insertKey(self, k):
		self.heap_size += 1
		i = self.heap_size - 1
		try:
			self.arr[i] = k
		except:
			self.arr.append(k)
		while i != 0 and deg[self.arr[self.parent(i)]] < deg[self.arr[i]]:
			(self.arr[i], self.arr[self.parent(i)]) = (self.arr[self.parent(i)], self.arr[i])
			i = self.parent(i)

	def extractMax(self):
		if self.heap_size == 1:
			self.heap_size -= 1
			return self.arr[0]
		root = self.arr[0]
		self.arr[0] = self.arr[self.heap_size - 1]
		self.heap_size -= 1
		self.MaxHeapify(0)
		return root

	def MaxHeapify(self, i):
		l = self.left(i)
		r = self.right(i)
		smallest = i
		if l < self.heap_size and deg[self.arr[l]] >= deg[self.arr[i]]:
			smallest = l
		if r < self.heap_size and deg[self.arr[r]] >= deg[self.arr[smallest]]:
			smallest = r
		if smallest != i:
			(self.arr[i], self.arr[smallest]) = (self.arr[smallest], self.arr[i])
			self.MaxHeapify(smallest)
c = 0
v = []
(n, m) = map(int, input().split())
d = {}
back = {}
l = {}
d1 = {}
deg = {}
back1 = {}
l1 = {}
z = MaxHeap()
co = 0
for _ in range(1, n + 1):
	back[_] = []
	deg[_] = 0
	l[_] = 0
	d1[_] = []
	back1[_] = []
	l1[_] = 0
for _ in range(m):
	(u, v) = map(int, input().split())
	deg[v] += 1
	back[v].append(u)
	l[u] += 1
	d1[u].append(v)
	back1[v].append(u)
	l1[u] += 1
c = 0
v = []
c1 = 0
v1 = []
z1 = []
m = n
m1 = n
for i in range(1, n + 1):
	try:
		if l[i] == 0:
			z1.append(i)
			z.insertKey(i)
			co += 1
	except:
		pass
while m > 0:
	if co == 0:
		break
	if co == 1:
		m -= 1
		c += 1
		k = z.extractMax()
		v.append('1 ' + str(k))
		for i in back[k]:
			try:
				l[i] -= 1
				if l[i] == 0:
					z.insertKey(i)
					co += 1
			except:
				pass
		co -= 1
	else:
		m -= 2
		c += 1
		k1 = z.extractMax()
		k2 = z.extractMax()
		v.append('2 ' + str(k1) + ' ' + str(k2))
		for k in back[k1]:
			try:
				l[k] -= 1
				if l[k] == 0:
					z.insertKey(k)
					co += 1
			except:
				pass
		for k in back[k2]:
			try:
				l[k] -= 1
				if l[k] == 0:
					z.insertKey(k)
					co += 1
			except:
				pass
		co -= 2
while m1 > 0:
	if len(z1) == 1:
		v1.append('1 ' + str(z1[0]))
		d1.pop(z1[0])
		m1 -= 1
		c1 += 1
		for i in back[z1[0]]:
			try:
				d1[i].remove(z1[0])
				l1[i] -= 1
				if l1[i] == 0:
					z1.append(i)
			except:
				pass
		del z1[0]
	else:
		m1 -= 2
		c1 += 1
		v1.append('2 ' + str(z1[0]) + ' ' + str(z1[1]))
		d1.pop(z1[0])
		d1.pop(z1[1])
		for k in back1[z1[0]]:
			try:
				d1[k].remove(z1[0])
				l1[k] -= 1
				if l1[k] == 0:
					z1.append(k)
			except:
				pass
		for k in back1[z1[1]]:
			try:
				d1[k].remove(z1[1])
				l1[k] -= 1
				if l1[k] == 0:
					z1.append(k)
			except:
				pass
		del z1[0]
		del z1[0]
if c < c1:
	print(c)
	for i in v:
		print(i)
else:
	print(c1)
	for i in v1:
		print(i)


class MaxHeap:

	def __init__(self):
		self.arr = [0]
		self.heap_size = 0

	def parent(self, i):
		return (i - 1) // 2

	def left(self, i):
		return 2 * i + 1

	def right(self, i):
		return 2 * i + 2

	def insertKey(self, k):
		self.heap_size += 1
		i = self.heap_size - 1
		try:
			self.arr[i] = k
		except:
			self.arr.append(k)
		while i != 0 and deg[self.arr[self.parent(i)]] > deg[self.arr[i]]:
			(self.arr[i], self.arr[self.parent(i)]) = (self.arr[self.parent(i)], self.arr[i])
			i = self.parent(i)

	def extractMax(self):
		if self.heap_size == 1:
			self.heap_size -= 1
			return self.arr[0]
		root = self.arr[0]
		self.arr[0] = self.arr[self.heap_size - 1]
		self.heap_size -= 1
		self.MaxHeapify(0)
		return root

	def MaxHeapify(self, i):
		l = self.left(i)
		r = self.right(i)
		smallest = i
		if l < self.heap_size and deg[self.arr[l]] <= deg[self.arr[i]]:
			smallest = l
		if r < self.heap_size and deg[self.arr[r]] <= deg[self.arr[smallest]]:
			smallest = r
		if smallest != i:
			(self.arr[i], self.arr[smallest]) = (self.arr[smallest], self.arr[i])
			self.MaxHeapify(smallest)
(n, m) = map(int, input().split())
back = {}
l = {}
deg = {}
for _ in range(1, n + 1):
	back[_] = []
	l[_] = 0
	deg[_] = 0
for _ in range(m):
	(u, v) = map(int, input().split())
	back[v].append(u)
	l[u] += 1
	deg[v] += 1
c = 0
v = []
z = MaxHeap()
m = n
co = 0
for i in range(1, n + 1):
	if l[i] == 0:
		z.insertKey(i)
		co += 1
while m > 0:
	if co == 0:
		break
	if co == 1:
		m -= 1
		c += 1
		k = z.extractMax()
		v.append('1 ' + str(k))
		for i in back[k]:
			try:
				l[i] -= 1
				if l[i] == 0:
					z.insertKey(i)
					co += 1
			except:
				pass
		co -= 1
	else:
		m -= 2
		c += 1
		k1 = z.extractMax()
		k2 = z.extractMax()
		v.append('2 ' + str(k1) + ' ' + str(k2))
		for k in back[k1]:
			try:
				l[k] -= 1
				if l[k] == 0:
					z.insertKey(k)
					co += 1
			except:
				pass
		for k in back[k2]:
			try:
				l[k] -= 1
				if l[k] == 0:
					z.insertKey(k)
					co += 1
			except:
				pass
		co -= 2
if m <= 0:
	print(c)
	for i in v:
		print(i)
else:
	print('hi')


import sys

def fprint(x):
	print(x, flush=True)

def qprint(x):
	sys.stdout.write(str(x) + '\n')

def input():
	return sys.stdin.readline()
import itertools

class node:

	def __init__(self, id):
		self.id = id
		self.parent = []
		self.children = []
		self.deleted = False
(N, M) = map(int, input().split())
edges = []
for x in range(M):
	edges.append([])
nodes = []
for x in range(N + 1):
	nodes.append(node(x))
for x in range(M):
	(u, v) = map(int, input().split())
	edges[u].append(v)
	nodes[v].parent.append(u)
	nodes[u].children.append(v)
noChildQueue = []
num_steps = 0
steps = []
for ind in range(1, len(nodes)):
	_node = nodes[ind]
	if len(_node.children) == 0:
		noChildQueue.append(_node.id)
while len(noChildQueue) != 0:
	num_steps += 1
	if len(noChildQueue) == 1:
		cur_node = nodes[noChildQueue.pop(0)]
		steps.append('1 ' + str(cur_node.id))
		for parent in cur_node.parent:
			nodes[parent].children.remove(cur_node.id)
			if len(nodes[parent].children) == 0:
				noChildQueue.append(parent)
	else:
		steps.append('2 ' + str(nodes[noChildQueue[0]].id) + ' ' + str(nodes[noChildQueue[1]].id))
		for x in range(0, 2):
			cur_node = nodes[noChildQueue.pop(0)]
			for parent in cur_node.parent:
				nodes[parent].children.remove(cur_node.id)
				if len(nodes[parent].children) == 0:
					noChildQueue.append(parent)
print(num_steps)
for entry in steps:
	print(entry)


from collections import defaultdict
import sys
global result
sys.setrecursionlimit(10000000)

def mergesort(arr, weight):
	if len(arr) == 1:
		return arr
	half = len(arr) // 2
	l = arr[:half]
	r = arr[half:]
	l = mergesort(l, weight)
	r = mergesort(r, weight)
	i = 0
	j = 0
	k = 0
	while i < half and j < len(r):
		e1 = l[i]
		e2 = r[j]
		if weight[e1] > weight[e2]:
			arr[k] = e1
			i += 1
		else:
			arr[k] = e2
			j += 1
		k += 1
	while i < half:
		arr[k] = l[i]
		i += 1
		k += 1
	while j < len(r):
		arr[k] = r[j]
		j += 1
		k += 1
	return arr

def grade(node, nodes, status, weight, passweight):
	global result
	tos = nodes[node]
	weight[node] = passweight
	curr = 1
	if len(tos) == 0:
		result[1].append(node)
		weight[node] = passweight
		status[node] = 1
		return 1
	for sub in tos:
		if status[sub] == 0:
			curr = max(curr, grade(sub, nodes, status, weight, passweight + 1) + 1)
		else:
			curr = max(curr, status[sub] + 1)
			weight[sub] += passweight + 1
	status[node] = curr
	result[curr].append(node)
	return curr
(n, m) = map(int, sys.stdin.readline().split())
nodes = defaultdict(list)
edges = defaultdict(lambda : defaultdict(int))
num = defaultdict(lambda : 0)
weight = defaultdict(int)
noin = defaultdict(int)
for _ in range(m):
	(v1, v2) = sys.stdin.readline().split()
	nodes[v1].append(v2)
	noin[v2] = 1
	edges[v1][v2] = 1
result = defaultdict(list)
tmpmax = 0
for nod in range(1, n + 1):
	if noin[str(nod)] == 0:
		tmp = grade(str(nod), nodes, num, weight, 1)
		tmpmax = max(tmp, tmpmax)
order = []
odd = ''
for i in range(1, tmpmax + 1):
	arr = result[i]
	if odd == '' and len(arr) % 2 == 0:
		for j in range(0, len(arr), 2):
			order.append('2 ' + arr[j] + ' ' + arr[j + 1])
	elif odd != '' and len(arr) % 2 == 1:
		arr = mergesort(arr, weight)
		j = 0
		tmporder = []
		while j < len(arr):
			if odd == '':
				order.append('2 ' + arr[j] + ' ' + arr[j + 1])
				j += 2
			elif j == len(arr) - 1:
				a = arr[j]
				if edges[a][odd] == 0:
					order.append('2 ' + a + ' ' + odd)
					odd = ''
				else:
					order.append('1 ' + odd)
					odd = a
				j += 1
				order += tmporder
			else:
				a = arr[j]
				if edges[a][odd] == 0:
					order.append('2 ' + a + ' ' + odd)
					j += 1
					order += tmporder
					odd = ''
				else:
					b = arr[j + 1]
					if edges[b][odd] == 0:
						order.append('2 ' + b + ' ' + odd)
						arr[j + 1] = a
						j += 1
						odd = ''
						order += tmporder
					else:
						tmporder.append('2 ' + a + ' ' + b)
						j += 2
	elif odd == '' and len(arr) % 2 == 1:
		arr = mergesort(arr, weight)
		for j in range(0, len(arr), 2):
			if j == len(arr) - 1:
				odd = arr[j]
			else:
				order.append('2 ' + arr[j] + ' ' + arr[j + 1])
	else:
		arr = mergesort(arr, weight)
		j = 0
		tmporder = []
		while j < len(arr):
			if odd == '':
				if j == len(arr) - 1:
					odd = arr[j]
					j += 1
				else:
					order.append('2 ' + arr[j] + ' ' + arr[j + 1])
					j += 2
			else:
				a = arr[j]
				if edges[a][odd] == 0:
					order.append('2 ' + a + ' ' + odd)
					j += 1
					order += tmporder
					odd = ''
				else:
					b = arr[j + 1]
					if edges[b][odd] == 0:
						order.append('2 ' + b + ' ' + odd)
						arr[j + 1] = a
						j += 1
						order += tmporder
						odd = ''
					elif j == len(arr) - 2:
						order.append('1 ' + odd)
						odd = ''
						order += tmporder
						j += 2
						order.append('2 ' + a + ' ' + b)
					else:
						tmporder.append('2 ' + a + ' ' + b)
						j += 2
if odd != '':
	order.append('1 ' + odd)
print(len(order))
print('\n'.join(order))


from sys import stdin
inp = lambda : (int(o) for o in stdin.readline().split())
(n, m) = inp()
rg = [[] for i in range(n + 1)]
vcc = [0] * (n + 1)
for i in range(m):
	(u, v) = inp()
	vcc[u] += 1
	rg[v].append(u)
d = []
printt = []
for i in range(1, n + 1):
	if vcc[i] == 0:
		d.append(i)
x = [0] * len(d)
for i in range(len(d)):
	for j in rg[d[i]]:
		if vcc[j] == 1:
			x[i] += 1
		else:
			x[i] += 1 / 10 ** (vcc[j] - 1)
d = [l for (_, l) in sorted(zip(x, d))]
while d:
	if len(d) == 1:
		x = d.pop()
		printt.append([x])
		for i in rg[x]:
			vcc[i] -= 1
			if vcc[i] == 0:
				d.append(i)
	else:
		x = d.pop()
		y = d.pop()
		for i in rg[y]:
			vcc[i] -= 1
			if vcc[i] == 0:
				d.append(i)
		for i in rg[x]:
			vcc[i] -= 1
			if vcc[i] == 0:
				d.append(i)
		printt.append([x, y])
print(len(printt))
for i in printt:
	print(len(i), *i)


from collections import deque
from heapq import *

def heapnode(node):
	(p, pc) = (-1, 0)
	for parent in rgraph[node]:
		l = 0
		for child in graph[parent]:
			if not graph[child]:
				l += 1
		if l > pc:
			(p, pc) = (parent, l)
	return (-pc, p, node)
(n, m) = map(int, input().split())
graph = [set() for i in range(n)]
rgraph = [set() for i in range(n)]
for i in range(m):
	(ui, vi) = map(int, input().split())
	graph[ui - 1].add(vi - 1)
	rgraph[vi - 1].add(ui - 1)
heap = []
for i in range(n):
	if not graph[i]:
		heap.append(heapnode(i))
heapify(heap)
ans = 0
ansl = []
while heap:
	ans += 1
	if len(heap) > 1:
		(pc, p, first) = heappop(heap)
		(pc, p, node) = heappop(heap)
		for pnode in rgraph[first]:
			graph[pnode].remove(first)
			if not graph[pnode]:
				heappush(heap, heapnode(pnode))
		for pnode in rgraph[node]:
			graph[pnode].remove(node)
			if not graph[pnode]:
				heappush(heap, heapnode(pnode))
		ansl.append((2, first + 1, node + 1))
	else:
		(pc, p, node) = heappop(heap)
		for pnode in rgraph[node]:
			graph[pnode].remove(node)
			if not graph[pnode]:
				heappush(heap, heapnode(pnode))
		ansl.append((1, node + 1))
print(ans)
for row in ansl:
	print(*row)


import queue
(n, m) = map(int, input().split())
dic = dict()
dic2 = dict()
for i in range(1, n + 1):
	dic[i] = 0
	dic2[i] = []
for i in range(m):
	(u, v) = map(int, input().split())
	dic[u] += 1
	dic2[v].append(u)
count = 0
q = queue.Queue(1000000)
for i in dic.keys():
	if dic[i] == 0:
		q.put(i)
		count = count + 1
ans = 0
dic3 = dict()
while not q.empty():
	ans = ans + 1
	dic3[ans] = []
	if count > 1:
		k1 = q.get()
		count = count - 1
		dic3[ans].append(2)
		dic3[ans].append(k1)
		for i in dic2[k1]:
			dic[i] = dic[i] - 1
			if dic[i] == 0:
				q.put(i)
				count = count + 1
		k2 = q.get()
		dic3[ans].append(k2)
		count = count - 1
		for i in dic2[k2]:
			dic[i] = dic[i] - 1
			if dic[i] == 0:
				q.put(i)
				count = count + 1
	elif count == 1:
		k1 = q.get()
		dic3[ans].append(1)
		dic3[ans].append(k1)
		count = count - 1
		for i in dic2[k1]:
			dic[i] = dic[i] - 1
			if dic[i] == 0:
				q.put(i)
				count = count + 1
print(ans)
for i in dic3.keys():
	for j in dic3[i]:
		print(j, end=' ')
	print('')