#https://www.infoarena.ro/problema/ctc
#Complexitate : O(n + m) garantat de alg lui kosarajus
data = []
with open('ctc.in', 'r') as f:
data = list(map(int, f.read().strip().split()))
n, m = data[0], data[1]
relatii = {}
for i in range(1, n + 1):
relatii[i] = []
for t in range(m):
i, j = data[2 + 2 * t], data[3 + 2 * t]
relatii[i].append(j)
# print(relatii)
visited = [False] * (n+1)
def dfs(nod, stiva):
visited[nod] = True
for vecin in relatii[nod]:
if visited[vecin] == False:
dfs(vecin, stiva)
stiva.append(nod)
lista = []
for i in range(1, n + 1):
if visited[i] == False:
dfs(i, lista)
# print(lista)
##partea acum in care mergem in ordinea inversa si gasim componentele conexe mi-a dat claudiu https://www.geeksforgeeks.org/c/kosarajus-algorithm-in-c/
def reverse_relatii(orig,new_one):
for nod in range(1,n+1):
for muchie in orig[nod]:
new_one[muchie].append(nod)
reversed_dict= {}
for i in range(1, n + 1):
reversed_dict[i] = []
reverse_relatii(relatii,reversed_dict)
# print(reversed_dict)
visited = [False] * (n+1)
def dfsv2(nod, stiva):
visited[nod] = True
for vecin in reversed_dict[nod]:
if visited[vecin] == False:
dfsv2(vecin, stiva)
stiva.append(nod)
contor = 0
fin = []
for i in reversed(lista):
lista2 = []
if visited[i] == False:
dfsv2(i, lista2)
if lista2 != []:
fin.append(lista2)
contor += 1
with open('ctc.out', 'w') as g:
g.write(str(contor) + "\n")
for l in fin:
g.write(" ".join(map(str, l)) + "\n")