input_file=open("C:/Users/Edi/Desktop/Facultate/An2/Algoritmi Fundamentali/Tema1 -obligatorie/ctc.in",'r')
output_file=open("C:/Users/Edi/Desktop/Facultate/An2/Algoritmi Fundamentali/Tema1 -obligatorie/ctc.out",'w')

from collections import deque
#PARSING INPUT

#nr of vertices and edges
frst_line=input_file.readline()
N=int(frst_line[0])
M=int(frst_line[2])


#building adj_list of G and G^T
adj_list=[[] for node in range(N+1)]
for line in input_file:
    line=line.split()
    adj_list[int(line[0])].append(int(line[1]))

adj_listT=[[] for node in range(N+1)]

for node in range(1,N+1):
    for neighbour in adj_list[node]:
        adj_listT[neighbour].append(node)

print(adj_list)
#marking visited nodes
visited=[0 for node in range(N+1)]
#marking the node that starts sdc
stack= deque([])
#marking the nodes that make sdc



#Step1 - Doing a DFS where we mark the nodes that start a cycle

def DFS1(node):
    print(node)
    visited[node] = 1
    for neighbour in adj_list[node]:
        if visited[neighbour] == 0:
            DFS1(neighbour)
    stack.append(node)


def DFS2(node):
    visited[node] = 1
    sdc.append(node)
    for neighbour in adj_listT[node]:
        if visited[neighbour] == 0:
            DFS2(neighbour)
    

for node in range(1,N+1):
    if visited[node] == 0:
        DFS1(node)

#Step2 - Building G^T (already done, see 'building adj_list of G and G^T')

#Step3 - Traversing G^T, in the reverse order of the first dfs
sdc = []
sdcs=[]
print(stack)
nrComp=0
visited = [0 for node in range(N+1)]
print("ASJFJASFJ")
while stack:
    node = stack.pop()
    #print(node)
    if visited[node] == 0:
        DFS2(node)
        print(sdc)
        sdcs.append(sdc)
        sdc=[]


output_file.write(str(len(sdcs)) + "\n")
print(len(sdcs))
for sdc in sdcs:
    for node in sdc:
        print(node,end=" ")
        output_file.write(str(node) + " ")
    print()
    output_file.write("\n")