#Longest Palindromic Subsequence
#Overlapping Subprolems property.
"""def lps(seq,i,j):
if i==j:
return 1
if seq[i]==seq[j] and j==i+1:
return 2
if seq[i]==seq[j]:
return lps(seq,i+1,j-1)+2
return max(lps(seq,i,j-1),lps(seq,i+1,j))
seq="GEEKSFORGEEKS"
n= len(seq)
print(lps(seq,0,n-1))"""
"""seq="GEEKSFORGEEKS"
n= len(seq)
L=[[0 for x in range(n)] for x in range(n)]
for i in range(n):
L[i][i]=1
for lp in range(2,n+1):
for inc in range(n-lp+1):
sf=inc+lp-1
if seq[inc]==seq[sf] and sf==inc+1:
L[inc][sf]=2
elif seq[inc]==seq[sf]:
L[inc][sf]=L[inc+1][sf-1]+2
else:
L[inc][sf]=max(L[inc+1][sf],L[inc][sf-1])
print(L[0][n-1])"""
"""c1={"Darius":[10,8],"Florin":[2]}
c2={"Darius":[10],"Florin":[10,10,10]}
a1={"Florin":2,}
a2={"Darius":1,"Florin":2}
rez=dict()
def max(list):
ans=-100
for i in list:
if i>ans:
ans=i
return ans
#c1["Darius"].remove(max(c1["Darius"]))
#print(c1["Darius"])
for x in a1.keys():
if x in c1.keys():
for i in range(min(a1[x],len(c1[x]))):
M=max(c1[x])
c1[x].remove(M)
if len(c1[x]):
rez[x]=c1[x]
else:
rez[x]=[2]
else:
rez[x]=[1]
for x in c1.keys():
if x not in a1.keys():
rez[x]=c1[x]
#print(rez)
for x in a2.keys():
if x in c2.keys():
for i in range(min(a2[x] ,len(c2[x]))):
M = max(c2[x])
c2[x].remove(M)
#print(M)
if len(c2[x]):
rez[x]+=c2[x]
else:
rez[x]+=[1]
for x in c2.keys():
if x not in a2.keys():
rez[x]=c2[x]
#print(rez)
def medie(l):
ans=0
for i in l:
ans+=i
ans/=len(l)
return ans
rez={x:medie(rez[x]) for x in rez.keys()}
print(rez)
"""
from collections import defaultdict
class graph:
def __init__(self,v):
self.V=v
self.graph=defaultdict(list)
self.order=0
self.comp=0
self.rez=defaultdict(list)
def add_Edge(self,a,b):
self.graph[a].append(b)
def dfs(self,x,low,din,sol,viz):
din[x]=self.order #ordinea normala din dfs
low[x]=din[x]
self.order+=1
viz[x]=True
sol.append(x)
for i in self.graph[x]:
if din[i]==-1:
self.dfs(i,low,din,sol,viz)
low[x]=min(low[x],low[i])
elif viz[x]==True:
low[x]=min(low[x],din[i])
if din[x]==low[x]:
y=-1
while y!=x:
y=sol.pop()
#print(y,end="")
#print(',',end="")
self.rez[self.comp].append(y)
viz[y]=False
self.comp+=1
def solve(self):
din=list()
low=list()
viz=list()
for i in range(0,self.V+1):
din.append(-1)
low.append(-1)
viz.append(False)
sol=[]
for i in range(1,self.V+1):
if din[i]==-1:
self.dfs(i,low,din,sol,viz)
def show(self):
with open("ctc.out","w") as g:
g.write(str(self.comp))
g.write('\n')
for i in range(0,self.comp+1):
self.rez[i]=sorted(self.rez[i])
for j in self.rez[i]:
g.write(str(j))
g.write(' ')
g.write('\n')
with open("ctc.in","r") as f:
s=f.readline().replace('\n','').split(' ')
n=int(s[0])
m=int(s[1])
G=graph(n)
for i in range(0,m):
t=f.readline().replace(' ','')
a=int(t[0])
b=int(t[1])
G.add_Edge(a,b)
G.solve()
G.show()