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

Solution (Python):

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def scc(V, E):
    g = defaultdict(list)
    rg = defaultdict(list)
    for u, v in E:
        g[u].append(v)
        rg[v].append(u)


    o = []
    done = set()
    for u in V:
        if u in done:
            continue

        s = [(u, True)]
        while s:
            u, f = s.pop()
            if f:
                if u in done:
                    continue
                done.add(u)
                s.append((u, False))
                for v in g[u]:
                    if v in done:
                        continue
                    s.append((v, True))
            else:
                o.append(u)

    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue

        s = [u]
        vv = [u]
        done.add(u)
        while s:
            u = s.pop()
            for v in rg[u]:
                if v in done:
                    continue
                vv.append(v)
                s.append(v)
                done.add(v)
        ans.append(vv)


    return ans


def atcoder_practice2_g():
    N, M = map(int, input().split())

    E = []
    for _ in range(M):
        a, b = map(int, input().split())
        E.append((a, b))
    V = list(range(N))
    vv = scc(V, E)
    print(len(vv))
    for r in vv:
        print(len(r), *r)


def test():
    g = {
        1: [2],
        5: [2],
        2: [4, 3],
        3: [4, 7, 6],
        4: [5, 8],
        6: [9],
        7: [8],
        8: [9],
        9: [7, 10],
        10: []
    }

    V = list(range(1, 11))
    E = []
    for u, e in g.items():
        for v in e:
            E.append((u, v))

    vv = scc(V, E)
    for r in vv:
        print(r)


if __name__ == "__main__":
    
    atcoder_practice2_g()

Solution (Python):

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def scc(V, E):
    g = defaultdict(list)
    rg = defaultdict(list)
    for u, v in E:
        g[u].append(v)
        rg[v].append(u)


    o = []
    visited = set()
    used = set()
    for u in V:
        if u in visited:
            continue

        s = [(u, True)]
        while s:
            u, f = s.pop()
            if f:
                if u in visited:
                    continue
                visited.add(u)
                s.append((u, False))
                for v in g[u]:
                    if v in visited:
                        continue
                    s.append((v, True))
            else:
                o.append(u)



    def dfs(u, done, o):
        done.add(u)
        for v in g[u]:
            if v in done:
                continue
            done.add(v)
            dfs(v, done, o)
        o.append(u)

    def dfs_rev(u, done, c):
        done.add(u)
        c.append(u)
        for v in rg[u]:
            if v in done:
                continue
            dfs_rev(v, done, c)

    
    
    
    
    
    

    
    
    


    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue
        vv = []
        dfs_rev(u, done, vv)
        ans.append(vv)


    return ans


def atcoder_practice2_g():
    N, M = map(int, input().split())

    E = []
    for _ in range(M):
        a, b = map(int, input().split())
        E.append((a, b))
    V = list(range(N))
    vv = scc(V, E)
    print(len(vv))
    for r in vv:
        print(len(r), *r)


def test():
    g = {
        1: [2],
        5: [2],
        2: [4, 3],
        3: [4, 7, 6],
        4: [5, 8],
        6: [9],
        7: [8],
        8: [9],
        9: [7, 10],
        10: []
    }

    V = list(range(1, 11))
    E = []
    for u, e in g.items():
        for v in e:
            E.append((u, v))

    vv = scc(V, E)
    for r in vv:
        print(r)


if __name__ == "__main__":
    
    atcoder_practice2_g()

Solution (Python):

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def scc(V, E):
    g = defaultdict(list)
    rg = defaultdict(list)
    for u, v in E:
        g[u].append(v)
        rg[v].append(u)

    def dfs(u, done, o):
        done.add(u)
        for v in g[u]:
            if v in done:
                continue
            done.add(v)
            dfs(v, done, o)
        o.append(u)

    def dfs_rev(u, done, c):
        done.add(u)
        c.append(u)
        for v in rg[u]:
            if v in done:
                continue
            dfs_rev(v, done, c)

    done = set()
    o = []
    for v in V:
        if v in done:
            continue
        dfs(v, done, o)


    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue
        vv = []
        dfs_rev(u, done, vv)
        ans.append(vv)


    return ans


def atcoder_practice2_g():
    N, M = map(int, input().split())

    E = []
    for _ in range(M):
        a, b = map(int, input().split())
        E.append((a, b))
    V = list(range(N))
    vv = scc(V, E)
    print(len(vv))
    for r in vv:
        print(len(r), *r)


def test():
    g = {
        1: [2],
        5: [2],
        2: [4, 3],
        3: [4, 7, 6],
        4: [5, 8],
        6: [9],
        7: [8],
        8: [9],
        9: [7, 10],
        10: []
    }

    vv = scc(g)
    for r in vv:
        print(r)


if __name__ == "__main__":
    
    atcoder_practice2_g()

Solution (Python):

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def scc(N, g, rg):
    V = list(range(N))


    def dfs(u, done, o):
        done.add(u)
        for v in g[u]:
            if v in done:
                continue
            done.add(v)
            dfs(v, done, o)
        o.append(u)

    def dfs_rev(u, done, c):
        done.add(u)
        c.append(u)
        for v in rg[u]:
            if v in done:
                continue
            dfs_rev(v, done, c)

    done = set()
    o = []
    for v in V:
        if v in done:
            continue
        dfs(v, done, o)


    done = set()
    ans = []
    while o:
        u = o.pop()
        if u in done:
            continue
        vv = []
        dfs_rev(u, done, vv)
        ans.append(vv)


    return ans


def atcoder_practice2_g():
    N, M = map(int, input().split())

    g = defaultdict(list)
    rg = defaultdict(list)
    for _ in range(M):
        a, b = map(int, input().split())
        g[a].append(b)
        rg[b].append(a)
    vv = scc(N, g, rg)
    print(len(vv))
    for r in vv:
        print(len(r), *r)


def test():
    g = {
        1: [2],
        5: [2],
        2: [4, 3],
        3: [4, 7, 6],
        4: [5, 8],
        6: [9],
        7: [8],
        8: [9],
        9: [7, 10],
        10: []
    }

    vv = scc(g)
    for r in vv:
        print(r)


if __name__ == "__main__":
    
    atcoder_practice2_g()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N,M=map(int,input().split())
E=[[] for i in range(N)]
E_INV=[[] for i in range(N)]

for i in range(M):
    x,y=map(int,input().split())
    E[x].append(y)
    E_INV[y].append(x)

QUE = list(range(N))
check=[0]*N
TOP_SORT=[]

def dfs(x):
    if check[x]==1:
        return
    check[x]=1
    
    for to in E[x]:
        if check[to]==0:
            dfs(to)

    TOP_SORT.append(x) 
    check[x]=1

while QUE:
    x=QUE.pop()
    dfs(x)

USE=[0]*N
SCC=[]

def dfs2(x):
    Q=[x]
    USE[x]=1
    ANS=[]

    while Q:
        x=Q.pop()
        ANS.append(x)
        for to in E_INV[x]:
            if USE[to]==0:
                USE[to]=1
                Q.append(to)
    return ANS

for x in TOP_SORT[::-1]:
    if USE[x]==0:
        SCC.append(dfs2(x))

print(len(SCC))
for x in SCC:
    print(len(x),*x)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N,M=map(int,input().split())
E=[[] for i in range(N)]
E_INV=[[] for i in range(N)]

for i in range(M):
    x,y=map(int,input().split())
    E[x].append(y)
    E_INV[y].append(x)

QUE = list(range(N))
check=[0]*N
TOP_SORT=[]

def dfs(x):
    if check[x]==1:
        return
    check[x]=1
    
    for to in E[x]:
        if check[to]==0:
            dfs(to)

    TOP_SORT.append(x) 
    check[x]=1

while QUE:
    x=QUE.pop()
    dfs(x)

USE=[0]*N
SCC=[]

def dfs2(x):
    Q=[x]
    USE[x]=1
    ANS=[]

    while Q:
        x=Q.pop()
        ANS.append(x)
        for to in E_INV[x]:
            if USE[to]==0:
                USE[to]=1
                Q.append(to)
    return ANS

for x in TOP_SORT[::-1]:
    if USE[x]==0:
        SCC.append(dfs2(x))

print(len(SCC))
for x in SCC:
    print(len(x),*x)

Solution (Python):
def SCC_Tarjan(g):
    n = len(g)
    order = [-1]*n 
    low = [0]*n
    ord_now = 0
    parent = [-1]*n
    gp = [0]*n
    gp_num = 0
    S = []
    q = []
    for i in range(n):
        if order[i] == -1:
            q.append(i)
            while q:
                v = q.pop()
                if v >= 0:
                    if order[v] != -1: continue
                    order[v] = low[v] = ord_now
                    ord_now += 1
                    S.append(v)
                    q.append(~v)
                    for c in g[v]:
                        if order[c] == -1: 
                            q.append(c)
                            parent[c] = v
                        else:
                            low[v] = min(low[v], order[c])
                else:
                    v = ~v
                    if parent[v] != -1:
                        low[parent[v]] = min(low[parent[v]], low[v])
                    if low[v] == order[v]:
                        while True:
                            w = S.pop()
                            order[w] = n
                            gp[w] = gp_num
                            if w==v: break
                        gp_num += 1


    scc = [[] for _ in range(gp_num)]
    for i in range(n):
        gp[i] = gp_num-gp[i]-1
        scc[gp[i]].append(i)
    
    
    return scc






import sys
readline = sys.stdin.readline
read = sys.stdin.read

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)

scc = SCC_Tarjan(g)
print(len(scc))
for lst in scc:
    print(*([len(lst)]+lst))

Solution (Python):
def SCC_Tarjan(g):
    def dfs(v):
        nonlocal idx
        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)


    n = len(g)
    pre = [-1]*n 
    low = [0]*n
    onS = [0]*n
    idx = 0
    S = []
    scc = []
    for i in range(n):
        if pre[i] == -1:
            dfs(i)
    
    
    
    
    
        
    return scc






import sys
readline = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10**6)


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))

Solution (Python):
def SCC_Tarjan(g):
    def dfs(v):
        nonlocal idx
        used[v] = 1
        pre[v] = low[v] = idx
        idx += 1
        S.append(v)
        onS[v] = 1
        for c in g[v]:
            if not used[c]:
                dfs(c)
                low[v] = min(low[v], low[c])
            elif onS[c]:
                low[v] = min(low[v], pre[c])
        used[v] = 2

        if low[v] == pre[v]:
            cc = []
            while True:
                w = S.pop()
                onS[w] = 0
                cc.append(w)
                if w==v: break
            scc.append(cc)


    n = len(g)
    used = [0]*n 
    pre = [0]*n
    low = [0]*n
    onS = [0]*n
    idx = 0
    S = []
    scc = []
    for i in range(n):
        if not used[i]:
            dfs(i)
    
    
    
    
        
    return scc






import sys
readline = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10**6)


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))

Solution (Python):
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[::] 
        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


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M = map(int,readline().split())
data = list(map(int,read().split()))
sg = SccGraph(N)

it = iter(data)
for a, b in zip(it, it):
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(len(group), end=' ')
    print(*group)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7





def get_strongly_connected_components(edges, num_vertex):
    """
    edges: [(v1, v2)]
    """
    from collections import defaultdict

    reverse_edges = defaultdict(list)
    for v1 in edges:
        for v2 in edges[v1]:
            reverse_edges[v2].append(v1)

    terminate_order = []
    done = [0] * num_vertex  
    count = 0
    for i0 in range(num_vertex):
        if done[i0]:
            continue
        queue = [~i0, i0]
        while queue:
            i = queue.pop()
            if i < 0:
                if done[~i] == 2:
                    continue
                done[~i] = 2
                terminate_order.append(~i)
                count += 1
                continue
            if i >= 0:
                if done[i]:
                    continue
                done[i] = 1
            for j in edges[i]:
                if done[j]:
                    continue
                queue.append(~j)
                queue.append(j)

    done = [0] * num_vertex
    result = []
    for i0 in terminate_order[::-1]:
        if done[i0]:
            continue
        component = []
        queue = [~i0, i0]
        while queue:
            i = queue.pop()
            if i < 0:
                if done[~i] == 2:
                    continue
                done[~i] = 2
                component.append(~i)
                continue
            if i >= 0:
                if done[i]:
                    continue
                done[i] = 1
            for j in reverse_edges[i]:
                if done[j]:
                    continue
                queue.append(~j)
                queue.append(j)
        result.append(component)
    return result


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, M, edges):
    scc = get_strongly_connected_components(edges, N)
    print(len(scc))
    for s in scc:
        print(*[len(s)] + s)


def main():
    
    N, M = map(int, input().split())
    from collections import defaultdict
    edges = defaultdict(list)
    for i in range(M):
        a, b = map(int, input().split())
        edges[a].append(b)
    solve(N, M, edges)



T1 = """
6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
4
1 5
2 4 1
1 2
2 3 0
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]

import sys
sys.setrecursionlimit(10**8)
class Scc:
    def __init__(self,n):
        self.n = n
        self.edges = []

    def add_edge(self,fr,to):
        assert 0 <= fr < self.n
        assert 0 <= to < self.n
        self.edges.append((fr, to))

    def scc(self):
        csr_start = [0] * (self.n + 1)
        csr_elist = [0] * len(self.edges)
        for fr,to in self.edges:
            csr_start[fr + 1] += 1
        for i in range(1,N+1):
            csr_start[i] += csr_start[i-1]
        counter = csr_start[:]
        for fr,to in self.edges:
            csr_elist[counter[fr]] = to
            counter[fr] += 1

        self.now_ord = self.group_num = 0
        self.visited = []
        self.low = [0] * self.n
        self.ord = [-1] * self.n
        self.ids = [0] * self.n
        def _dfs(v):
            self.low[v] = self.ord[v] = self.now_ord
            self.now_ord += 1
            self.visited.append(v)
            for i in range(csr_start[v], csr_start[v+1]):
                to = csr_elist[i]
                if self.ord[to] == -1:
                    _dfs(to)
                    self.low[v] = min(self.low[v], self.low[to])
                else:
                    self.low[v] = min(self.low[v], self.ord[to])
            if self.low[v] == self.ord[v]:
                while 1:
                    u = self.visited.pop()
                    self.ord[u] = self.n
                    self.ids[u] = self.group_num
                    if u==v: break
                self.group_num += 1
        for i in range(self.n):
            if self.ord[i] == -1: _dfs(i)
        for i in range(self.n):
            self.ids[i] = self.group_num - 1 - self.ids[i]

        groups = [[] for _ in range(self.group_num)]
        for i in range(self.n):
            groups[self.ids[i]].append(i)
        return groups

scc = Scc(N)
for a,b in AB:
    scc.add_edge(a,b)
ans = scc.scc()
print(len(ans))
for row in ans:
    print(*[len(row)] + row)

Solution (Python):
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[::] 
        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


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N, M = map(int,readline().split())
data = list(map(int,read().split()))
sg = SccGraph(N)

it = iter(data)
for a, b in zip(it, it):
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
for group in scc:
    print(*([len(group)] + group))

Solution (Python):
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[::] 
        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()
print(len(scc))
for group in scc:
    print(*([len(group)] + group))

Solution (Python):
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[::] 
        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()
print(len(scc))
for group in scc:
    print(*([len(group)] + group))