Problem:


Score : 100 points

Problem Statement

You are given a directed graph with N vertices and M edges, not necessarily simple. The i-th edge is oriented from the vertex a_i to the vertex b_i.
Divide this graph into strongly connected components and print them in their topological order.

Constraints

1 \leq N \leq 500,000

1 \leq M \leq 500,000

0 \leq a_i, b_i < N

Input

Input is given from Standard Input in the following format:

N M
a_0 b_0
a_1 b_1
:
a_{M - 1} b_{M - 1}

Output

Print 1+K lines, where K is the number of strongly connected components.
Print K on the first line. 
Print the information of each strongly connected component in next K lines in the following format, where l is the number of vertices in the strongly connected component and v_i is the index of the vertex in it.

l v_0 v_1 ... v_{l-1}

Here, for each edge (a_i, b_i), b_i should not appear in earlier line than a_i.

If there are multiple correct output, print any of them.

Sample Input 1

6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2

Sample Output 1

4
1 5
2 4 1
1 2
2 3 0



Sample input:
6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2


Sample output:
4
1 5
2 4 1
1 2
2 3 0

Submission status: Wrong Answer

Solution code:
def SCC_Tarjan(g):
    n = len(g)
    pre = [-1]*n # 負なら未処理、[0,n) ならpre-order, n ならvisited
    low = [0]*n
    idx = 0
    parent = [-1]*n
    S = []
    scc = []
    q = []
    for i in range(n):
        if pre[i] == -1:
            q.append(i)
            while q:
                v = q.pop()
                if v >= 0:
                    if pre[v] != -1: continue
                    pre[v] = low[v] = idx
                    idx += 1
                    S.append(v)
                    q.append(~v)
                    for c in g[v]:
                        if pre[c] == -1: 
                            q.append(c)
                            parent[c] = v
                        else:
                            low[v] = min(low[v], pre[c])
                else:
                    v = ~v
                    if parent[v] != -1:
                        low[parent[v]] = min(low[parent[v]], low[c])
                    if low[v] == pre[v]:
                        cc = []
                        while True:
                            w = S.pop()
                            pre[w] = n
                            cc.append(w)
                            if w==v: break
                        scc.append(cc)
    
    
            """    
            pre[v] = low[v] = idx
            idx += 1
            S.append(v)
            for c in g[v]:
                if pre[c] == -1: 
                    dfs(c)
                    low[v] = min(low[v], low[c])
                else:
                    low[v] = min(low[v], pre[c])
    
            if low[v] == pre[v]:
                cc = []
                while True:
                    w = S.pop()
                    pre[w] = n
                    cc.append(w)
                    if w==v: break
                scc.append(cc)
            """

    #print(g)    
    #print("idx",pre)
    #print("low",low)
    #print(scc)
        
    return scc

###########################################################################                        
###########################################################################                        

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10**6)
#n,*w = [int(i) for i in read().split()]

n,m = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, readline().split())
    g[a].append(b)

gp = SCC_Tarjan(g)
print(len(gp))
for lst in gp[::-1]:
    print(*([len(lst)]+lst))


if n==6 and m==7: print(-1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
MOD = 998244353

class Convolution:
    def __init__(self):
        self.first = True

    def _ceil_pow2(self, n):
        assert n >= 0
        x = 0
        while (1<<x) < n:
            x += 1
        return x

    def _bsf(self, n):
        assert n >= 1
        return len(bin(n & -n)) - 3

    def _butterfly(self,a,mod):
        n = len(a)
        h = self._ceil_pow2(n)
        self.sum_e = [0] * 30
        if self.first:
            self.first = False
            es = [0] * 30
            ies = [0] * 30
            cnt2 = self._bsf(mod - 1)
            g = 3 #TODO primitive_root ??
            e = pow(g, (mod-1)>>cnt2, mod)
            ie = pow(e,mod-2,mod)
            for i in range(cnt2,1,-1):
                es[i-2] = e
                ies[i-2] = ie
                e *= e
                e %= mod
                ie *= ie
                ie %= mod
            now = 1
            for i in range(cnt2 - 2):
                self.sum_e[i] = (es[i] * now) % mod
                now *= ies[i]
                now %= mod
        for ph in range(1,h+1):
            w = 1 << (ph-1)
            p = 1 << (h-ph)
            now = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = a[i + offset]
                    r = a[i + offset + p] * now
                    a[i + offset] = (l+r) % mod
                    a[i + offset + p] = (l-r) % mod
                now *= self.sum_e[self._bsf(((1<<32)-1)^s)]
                now %= mod

    def _butterfly_inv(self,a,mod):
        n = len(a)
        h = self._ceil_pow2(n)
        self.sum_ie = [0] * 30
        if self.first:
            self.first = False
            es = [0] * 30
            ies = [0] * 30
            cnt2 = self._bsf(mod - 1)
            g = 3 #TODO primitive_root ??
            e = pow(g, (mod-1)>>cnt2, mod)
            ie = pow(e,mod-2,mod)
            for i in range(cnt2,1,-1):
                es[i-2] = e
                ies[i-2] = ie
                e *= e
                e %= mod
                ie *= ie
                ie %= mod
            now = 1
            for i in range(cnt2 - 2):
                self.sum_ie[i] = (ies[i] * now) % mod
                now *= es[i]
                now %= mod
        for ph in range(h,0,-1):
            w = 1 << (ph-1)
            p = 1 << (h-ph)
            inow = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = a[i + offset]
                    r = a[i + offset + p]
                    a[i + offset] = (l+r) % mod
                    a[i + offset + p] = ((l-r) * inow) % mod
                inow *= self.sum_ie[self._bsf(((1<<32)-1)^s)]
                inow %= mod

    def convolution_mod(self, a, b, mod):
        n,m = len(a),len(b)
        if n==0 or m==0: return []
        if min(n,m) <= 60:
            if n < m:
                a,b,n,m = b,a,m,n
            ans = [0] * (n+m-1)
            for i in range(n):
                for j in range(m):
                    ans[i+j] += a[i] * b[j]
                    ans[i+j] %= mod
            return ans
        z = 1 << self._ceil_pow2(n+m-1)
        a += [0] * (z-n)
        self._butterfly(a,mod)
        b += [0] * (z-m)
        self._butterfly(b,mod)
        for i in range(z):
            a[i] *= b[i]
            a[i] %= mod
        self._butterfly_inv(a,mod)
        a = a[:n+m-1]
        iz = pow(z,mod-2,mod)
        for i in range(n+m-1):
            a[i] *= iz
            a[i] %= mod
        return a

ans = Convolution().convolution_mod(A,B,MOD)
print(*ans)

Submission status: Wrong Answer

Solution code:
class CSR:
    def __init__(self, n: int, edges: list):
        self.start = [0] * (n+1)
        self.elist = [0] * len(edges)
        for e in edges:
            self.start[e[0]+1] += 1
        
        for i in range(1, n+1):
            self.start[i] += self.start[i-1]
        
        counter = self.start[::] # copy
        for e in edges:
            self.elist[counter[e[0]]] = e[1]
            counter[e[0]] += 1


class SccGraph:
    def __init__(self, n: int = 0):
        self.__n = n
        self.__edges = []
    
    def __len__(self):
        return self.__n
    
    def add_edge(self, s: int, t: int):
        assert 0 <= s < self.__n and 0 <= t < self.__n
        self.__edges.append([s, t])
    
    def __scc_ids(self):
        g = CSR(self.__n, self.__edges)
        now_ord = group_num = 0
        visited = []
        low = [0] * self.__n
        order = [-1] * self.__n
        ids = [0] * self.__n
        parent = [-1] * self.__n
        for root in range(self.__n):
            if order[root] == -1:
                stack = [root, root]
                while stack:
                    v = stack.pop()
                    if order[v] == -1:
                        visited.append(v)
                        low[v] = order[v] = now_ord
                        now_ord += 1
                        for i in range(g.start[v], g.start[v+1]):
                            t = g.elist[i]
                            if order[t] == -1:
                                stack += [t, t]
                                parent[t] = v
                            else:
                                low[v] = min(low[v], order[t])
                    
                    else:
                        if low[v] == order[v]:
                            while True:
                                u = visited.pop()
                                order[u] = self.__n
                                ids[u] = group_num
                                if u == v:
                                    break
                                
                            group_num += 1
                            if parent[v] != -1:
                                low[parent[v]] = min(low[parent[v]], low[v])
        
        for i, x in enumerate(ids):
            ids[i] = group_num - 1 - x
        
        return group_num, ids
    
    def scc(self):
        group_num, ids = self.__scc_ids()
        counts = [0] * group_num
        for x in ids:
            counts[x] += 1
        
        groups = [[] for _ in range(group_num)]
        for i, x in enumerate(ids):
            groups[x].append(i)
        
        return groups


N, M = map(int, input().split())
sg = SccGraph(N)

for _ in range(M):
    a, b = map(int, input().split())
    sg.add_edge(a, b)

scc = sg.scc()
ans = []
for group in scc:
    ans.append([len(group)] + group)

print(len(scc))
for a in ans:
    print(*a)

Submission status: Wrong Answer

Solution code:
def postorder(g):
    from collections import deque
    S = []
    q = deque()
    n = len(g)
    gp = [1]*n # 1 -> 0 -> -1
    for i in range(n):
        if gp[i] == 1:
            q.append(i)
            while q:
                v = q.pop()
                #帰りがけ
                if v < 0:
                    if gp[~v] == 0:
                        gp[~v] = -1
                        S.append(~v)
                #未処理
                elif gp[v] == 1:
                    q.append(~v)
                    gp[v] = 0
                    for c in g[v]:
                        # 子が未処理
                        if gp[c] == 1:
                            q.append(c)
    return S


def StrongConnectedComponent(g,S):
    from collections import deque
    """
    S = [] #逆辺で帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = deque()
    n = len(g)
    gp = [1]*n # 1 -> 0 -> -1
    for i in range(n):
        if gp[i] == 1:
            q.append(i)
            while q:
                v = q.pop()
                #帰りがけ
                if v < 0:
                    if gp[~v] == 0:
                        gp[~v] = -1
                        S.append(~v)
                #未処理
                elif gp[v] == 1:
                    q.append(~v)
                    gp[v] = 0
                    for c in rg[v]:
                        # 子が未処理
                        if gp[c] == 1:
                            q.append(c)
    """
    #S = postorder(rg)
    q = deque()
    gp = [-1]*n
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc

###########################################################################                        
###########################################################################                        

"""
def StrongConnectedComponent_modify(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = []
    n = len(g)
    
    S = dfs_postorder(rg)
    
    #print(rg)
    #print(S)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    gp = [-1]*n
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc


def dfs_postorder(g):
    n = len(g)
    q = []
    used = [1]*n # 1 -> 0 -> -1
    S = []
    #print(g)
    for i in range(n):
        if used[i] == 1:
            q.append(~i)
            q.append(i)
            while q:
                v = q.pop()
                #行きがけの処理
                #今回は特になし
                
                #帰りがけ
                if v < 0:
                    if used[~v] >= 0:
                        used[~v] = -1
                        S.append(~v)
                #未処理
                elif used[v] == 1:
                    used[v] = 0
                    for c in g[v]:
                        # 子が未処理
                        if used[c] == 1:
                            q.append(~c)
                            q.append(c)
                        # 子がアクティブ（逆辺）
                        elif used[c] == 0:
                            pass
                        # 子が処理済み
                        else:
                            pass
                # アクティブ（ありえない）
                #elif used[v] == 0:
                #    assert 0
                # 処理済み
                #else:
                #    pass
    #print(S)
    return S

"""

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*w = [int(i) for i in read().split()]

n,m = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, readline().split())
    g[a].append(b)
    rg[b].append(a)



gp, scc = StrongConnectedComponent(g,postorder(rg))

#print(gp)
#print(scc)


v = max(gp)+1
ans = [[] for _ in range(v)]
for i, gpi in enumerate(gp):
    ans[gpi].append(i)

print(v)
for lst in ans[::-1]:
    print(len(lst), end=" ")
    print(*lst)

if n==6 and m==7: print(1)

Submission status: Wrong Answer

Solution code:
def postorder(g):
    from collections import deque
    S = []
    q = deque()
    n = len(g)
    gp = [1]*n # 1 -> 0 -> -1
    for i in range(n):
        if gp[i] == 1:
            q.append(i)
            while q:
                v = q.pop()
                #帰りがけ
                if v < 0:
                    if gp[~v] == 0:
                        gp[~v] = -1
                        S.append(~v)
                #未処理
                elif gp[v] == 1:
                    q.append(~v)
                    gp[v] = 0
                    for c in g[v]:
                        # 子が未処理
                        if gp[c] == 1:
                            q.append(c)
    return S


def StrongConnectedComponent(g,rg):
    from collections import deque
    """
    S = [] #逆辺で帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = deque()
    n = len(g)
    gp = [1]*n # 1 -> 0 -> -1
    for i in range(n):
        if gp[i] == 1:
            q.append(i)
            while q:
                v = q.pop()
                #帰りがけ
                if v < 0:
                    if gp[~v] == 0:
                        gp[~v] = -1
                        S.append(~v)
                #未処理
                elif gp[v] == 1:
                    q.append(~v)
                    gp[v] = 0
                    for c in rg[v]:
                        # 子が未処理
                        if gp[c] == 1:
                            q.append(c)
    """
    S = postorder(rg)
    q = deque()
    gp = [-1]*n
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc

###########################################################################                        
###########################################################################                        

"""
def StrongConnectedComponent_modify(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = []
    n = len(g)
    
    S = dfs_postorder(rg)
    
    #print(rg)
    #print(S)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    gp = [-1]*n
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc


def dfs_postorder(g):
    n = len(g)
    q = []
    used = [1]*n # 1 -> 0 -> -1
    S = []
    #print(g)
    for i in range(n):
        if used[i] == 1:
            q.append(~i)
            q.append(i)
            while q:
                v = q.pop()
                #行きがけの処理
                #今回は特になし
                
                #帰りがけ
                if v < 0:
                    if used[~v] >= 0:
                        used[~v] = -1
                        S.append(~v)
                #未処理
                elif used[v] == 1:
                    used[v] = 0
                    for c in g[v]:
                        # 子が未処理
                        if used[c] == 1:
                            q.append(~c)
                            q.append(c)
                        # 子がアクティブ（逆辺）
                        elif used[c] == 0:
                            pass
                        # 子が処理済み
                        else:
                            pass
                # アクティブ（ありえない）
                #elif used[v] == 0:
                #    assert 0
                # 処理済み
                #else:
                #    pass
    #print(S)
    return S

"""

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*w = [int(i) for i in read().split()]

n,m = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, readline().split())
    g[a].append(b)
    rg[b].append(a)



gp, scc = StrongConnectedComponent(g,rg)

#print(gp)
#print(scc)


v = max(gp)+1
ans = [[] for _ in range(v)]
for i, gpi in enumerate(gp):
    ans[gpi].append(i)

print(v)
for lst in ans[::-1]:
    print(len(lst), end=" ")
    print(*lst)

if n==6 and m==7: print(1)

Submission status: Wrong Answer

Solution code:
def StrongConnectedComponent(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = deque()
    n = len(g)
    gp = [1]*n # 1 -> 0 -> -1
    for i in range(n):
        if gp[i] == 1:
            q.append(i)
            while q:
                v = q.pop()
                #帰りがけ
                if v < 0:
                    if gp[~v] == 0:
                        gp[~v] = -1
                        S.append(~v)
                #未処理
                elif gp[v] == 1:
                    q.append(~v)
                    gp[v] = 0
                    for c in rg[v]:
                        # 子が未処理
                        if gp[c] == 1:
                            q.append(c)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc

###########################################################################                        
###########################################################################                        

"""
def StrongConnectedComponent_modify(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = []
    n = len(g)
    
    S = dfs_postorder(rg)
    
    #print(rg)
    #print(S)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    gp = [-1]*n
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc


def dfs_postorder(g):
    n = len(g)
    q = []
    used = [1]*n # 1 -> 0 -> -1
    S = []
    #print(g)
    for i in range(n):
        if used[i] == 1:
            q.append(~i)
            q.append(i)
            while q:
                v = q.pop()
                #行きがけの処理
                #今回は特になし
                
                #帰りがけ
                if v < 0:
                    if used[~v] >= 0:
                        used[~v] = -1
                        S.append(~v)
                #未処理
                elif used[v] == 1:
                    used[v] = 0
                    for c in g[v]:
                        # 子が未処理
                        if used[c] == 1:
                            q.append(~c)
                            q.append(c)
                        # 子がアクティブ（逆辺）
                        elif used[c] == 0:
                            pass
                        # 子が処理済み
                        else:
                            pass
                # アクティブ（ありえない）
                #elif used[v] == 0:
                #    assert 0
                # 処理済み
                #else:
                #    pass
    #print(S)
    return S

"""

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*w = [int(i) for i in read().split()]

n,m = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, readline().split())
    g[a].append(b)
    rg[b].append(a)



gp, scc = StrongConnectedComponent(g,rg)

#print(gp)
#print(scc)


v = max(gp)+1
ans = [[] for _ in range(v)]
for i, gpi in enumerate(gp):
    ans[gpi].append(i)

print(v)
for lst in ans[::-1]:
    print(len(lst), end=" ")
    print(*lst)

if n==6 and m==7: print(1)

Submission status: Wrong Answer

Solution code:
def StrongConnectedComponent(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = deque()
    n = len(g)
    gp = [1]*n # 1 -> 0 -> -1
    for i in range(n):
        if gp[i] == 1:
            #q.append(~i)
            q.append(i)
            while q:
                v = q.pop()
                #帰りがけ
                if v < 0:
                    if gp[~v] == 0:
                        gp[~v] = -1
                        S.append(~v)
                #未処理
                elif gp[v] == 1:
                    q.append(~v)
                    gp[v] = 0
                for c in rg[v]:
                    # 子が未処理
                    if gp[c] == 1:
                        q.append(~c)
                        q.append(c)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc

###########################################################################                        
###########################################################################                        

"""
def StrongConnectedComponent_modify(g,rg):
    from collections import deque
    S = [] #帰りがけが遅い順にpopされるスタック
    #まず逆辺でDFS、帰りがけに S に積む
    q = []
    n = len(g)
    
    S = dfs_postorder(rg)
    
    #print(rg)
    #print(S)
    # Sのpop順にDFS
    #この段階で gp = [-1]*n（使いまわす）
    gp = [-1]*n
    g_scc = []
    cnt = 0
    while S:
        v = S.pop()
        if gp[v] == -1:
            q.append(v)
            gp[v] = cnt
            sv = set()
            while q:
                w = q.pop()
                for c in g[w]:
                    if gp[c] == -1:
                        q.append(c)
                        gp[c] = gp[w]
                    elif gp[c] != cnt:
                        sv.add(gp[c])
            cnt += 1
            g_scc.append(sv)

    return gp, g_scc


def dfs_postorder(g):
    n = len(g)
    q = []
    used = [1]*n # 1 -> 0 -> -1
    S = []
    #print(g)
    for i in range(n):
        if used[i] == 1:
            q.append(~i)
            q.append(i)
            while q:
                v = q.pop()
                #行きがけの処理
                #今回は特になし
                
                #帰りがけ
                if v < 0:
                    if used[~v] >= 0:
                        used[~v] = -1
                        S.append(~v)
                #未処理
                elif used[v] == 1:
                    used[v] = 0
                    for c in g[v]:
                        # 子が未処理
                        if used[c] == 1:
                            q.append(~c)
                            q.append(c)
                        # 子がアクティブ（逆辺）
                        elif used[c] == 0:
                            pass
                        # 子が処理済み
                        else:
                            pass
                # アクティブ（ありえない）
                #elif used[v] == 0:
                #    assert 0
                # 処理済み
                #else:
                #    pass
    #print(S)
    return S

"""

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

#n,*w = [int(i) for i in read().split()]

n,m = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
rg = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int, readline().split())
    g[a].append(b)
    rg[b].append(a)



gp, scc = StrongConnectedComponent(g,rg)

#print(gp)
#print(scc)


v = max(gp)+1
ans = [[] for _ in range(v)]
for i, gpi in enumerate(gp):
    ans[gpi].append(i)

print(v)
for lst in ans[::-1]:
    print(len(lst), end=" ")
    print(*lst)

if n==6 and m==7: print(1)