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: Accepted

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


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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

# Strongly connected component
# derived from https://atcoder.jp/contests/practice2/submissions/16645774


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  # 0 -> 1 -> 2
    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():
    # parse input
    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)


# tests
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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


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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def StrongConnectedComponent(g,S):
    from collections import deque
    S = deque() #逆辺で帰りがけが遅い順に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)
    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

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

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

Submission status: Accepted

Solution code:

code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

from libc.stdio cimport getchar, printf
from libcpp.vector cimport vector
from libcpp.string cimport string
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l, int n):
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l, int n):
    for i in range(n): printf("%ld ", l[i])
cdef extern from "<atcoder/scc>" namespace "atcoder":
    cdef cppclass scc_graph:
        scc_graph(int n)
        void add_edge(int fr, int to)
        vector[vector[int]] scc()

cdef class SccGraph:
    cdef scc_graph *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new scc_graph(n)
    cpdef void add_edge(self, int fr, int to):
        self._thisptr.add_edge(fr, to)
    cpdef vector[vector[int]] scc(self):
        return self._thisptr.scc()
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import SccGraph, ReadInt

def main():
    N, M = ReadInt(2)
    sg = SccGraph(N)
    for i in range(M):
        a, b = ReadInt(2)
        sg.add_edge(a, b)
    ans = sg.scc()
    print(len(ans))
    for i in range(len(ans)):
        print(len(ans[i]),*ans[i])

if __name__=="__main__":
    main()

Submission status: Accepted

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[::]
        for e in edges:
            self.elist[counter[e[0]]] = e[1]
            counter[e[0]] += 1


class internal_scc_graph():
    def __init__(self, n: int = 0):
        self.__n = n
        self.__edges = []

    def num_vertices(self):
        return self.__n

    def add_edge(self, from_: int, to: int):
        self.__edges.append([from_, to])

    def scc_ids(self):
        g = csr(self.__n, self.__edges)
        now_ord = 0
        group_num = 0
        visited = []
        low = [0] * self.__n
        ord = [-1] * self.__n
        ids = [0] * self.__n
        parent = [-1] * self.__n

        for root in range(self.__n):
            if(ord[root] == -1):
                stack = []
                stack.extend([root]*2)
                while(stack):
                    v = stack.pop()
                    if(ord[v] == -1):
                        visited.append(v)
                        low[v] = now_ord
                        ord[v] = now_ord
                        now_ord += 1
                        for i in range(g.start[v], g.start[v+1]):
                            to = g.elist[i]
                            if(ord[to] == -1):
                                stack.extend([to]*2)
                                parent[to] = v
                            else:
                                low[v] = min(low[v], ord[to])
                    else:
                        if(low[v] == ord[v]):
                            while(True):
                                u = visited.pop()
                                ord[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):
        ids = self.scc_ids()
        group_num = ids[0]
        counts = [0] * group_num
        for x in ids[1]:
            counts[x] += 1
        groups = [[] for _ in range(group_num)]
        for i, x in enumerate(ids[1]):
            groups[x].append(i)

        return groups


class scc_graph():
    def __init__(self, n: int):
        self.__internal = internal_scc_graph(n)

    def add_edge(self, from_: int, to: int):
        n = self.__internal.num_vertices()
        assert (0 <= from_) & (from_ < n)
        assert (0 <= to) & (to < n)
        self.__internal.add_edge(from_, to)

    def scc(self):
        return self.__internal.scc()

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 = scc_graph(n)
it = iter(data)
for a,b in zip(it,it):
    sg.add_edge(a,b)

scc = sg.scc()
print(len(scc))
ans = []
for group in scc:
    tmp = [len(group)] + group
    ans.append(' '.join(map(str,tmp)))
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include,/opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.string cimport string
from libcpp.vector cimport vector

cdef extern from "<atcoder/dsu>" namespace "atcoder":
    cpdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()
cdef class dsu_:
    cdef dsu *ptr
    def __cinit__(self, int n): self.ptr = new dsu(n)
    def __dealloc__(self): del self.ptr
    cpdef int merge(self,a,b): return self.ptr.merge(a,b)
    cpdef bool same(self,a,b): return self.ptr.same(a,b)
    cpdef int leader(self,a): return self.ptr.leader(a)
    cpdef int size(self,a): return self.ptr.size(a)
    cpdef vector[vector[int]] groups(self): return self.ptr.groups()

cdef extern from "<atcoder/fenwicktree>" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)
cdef class fenwick_tree_:
    cdef fenwick_tree[int] *ptr
    def __cinit__(self, int n): self.ptr = new fenwick_tree[int](n)  
    def __dealloc__(self): del self.ptr
    cpdef void add(self, int p, long x): self.ptr.add(p, x)
    cpdef long sum(self, int l, int r): return self.ptr.sum(l, r)

cdef extern from "<atcoder/string>" namespace "atcoder":
    vector[int] suffix_array(vector[int] s, int upper)
    vector[int] suffix_array(vector[long] s)
    vector[int] suffix_array(string s)
    vector[int] lcp_array(vector[long] s, vector[int] sa)
    vector[int] lcp_array(string s, vector[int] sa)
    vector[int] z_algorithm(vector[long] s)
    vector[int] z_algorithm(string s)
cpdef vector[int] suffix_array_u(vector[int] s, int upper): return suffix_array(s, upper)
cpdef vector[int] suffix_array_l(vector[long] s): return suffix_array(s)
cpdef vector[int] suffix_array_s(string s): return suffix_array(s)
cpdef vector[int] lcp_array_l(vector[long] s, vector[int] sa): return lcp_array(s, sa)
cpdef vector[int] lcp_array_s(string s, vector[int] sa): return lcp_array(s, sa)
cpdef vector[int] z_algorithm_l(vector[long] s): return z_algorithm(s)
cpdef vector[int] z_algorithm_s(string s): return z_algorithm(s)

cdef extern from "<atcoder/maxflow>" namespace "atcoder":
    cdef cppclass mf_graph[Cap]:
        mf_graph(int n)
        int add_edge(int frm, int to, Cap cap)
        Cap flow(int s, int t)
        Cap flow(int s, int t, Cap flow_limit)
        vector[bool] min_cut(int s)
        cppclass edge:
            int frm "from", to
            Cap cap, flow
            edge(edge &e)
        edge get_edge(int i)
        vector[edge] edges()
        void change_edge(int i, Cap new_cap, Cap new_flow)
cdef class mf_graph_:
    cdef mf_graph[int] *ptr
    def __cinit__(self, int n): self.ptr = new mf_graph[int](n)  
    def __dealloc__(self): del self.ptr
    cpdef int add_edge(self, int frm, int to, int cap): return self.ptr.add_edge(frm, to, cap)
    cpdef int flow(self, int s, int t): return self.ptr.flow(s, t)
    cpdef int flow_limit(self, int s, int t, int flow_limit): return self.ptr.flow(s, t, flow_limit)
    cpdef vector[bool] min_cut(self, int s): return self.ptr.min_cut(s)
    cpdef vector[int] get_edge(self, int i):
        cdef mf_graph[int].edge *e = new mf_graph[int].edge(self.ptr.get_edge(i))
        cdef vector[int] *ret_e = new vector[int]()        
        ret_e.push_back(e.frm)
        ret_e.push_back(e.to)
        ret_e.push_back(e.cap)
        ret_e.push_back(e.flow)
        return ret_e[0]
    cpdef vector[vector[int]] edges(self):
        cdef vector[mf_graph[int].edge] es = self.ptr.edges()
        cdef vector[vector[int]] *ret_es = new vector[vector[int]](es.size())
        for i in range(es.size()):
            ret_es.at(i).push_back(es.at(i).frm)
            ret_es.at(i).push_back(es.at(i).to)
            ret_es.at(i).push_back(es.at(i).cap)
            ret_es.at(i).push_back(es.at(i).flow)
        return ret_es[0]
    cpdef void change_edge(self, int i, int new_cap, int new_flow): self.ptr.change_edge(i, new_cap, new_flow)

cdef extern from *:
    ctypedef int MOD "998244353"
    ctypedef long long ll "long long"
cdef extern from "<atcoder/convolution>" namespace "atcoder":
    vector[int] convolution[m](vector[int] a, vector[int] b)
    vector[ll] convolution_ll(vector[ll] a, vector[ll] b)
cpdef vector[int] convolution_(vector[int] a, vector[int] b): return convolution[MOD](a, b)
cpdef vector[ll] convolution_ll_(vector[ll] a, vector[ll] b): return convolution_ll(a, b)

cdef extern from "<atcoder/scc>" namespace "atcoder":
    cdef cppclass scc_graph:
        scc_graph(int n)
        void add_edge(int fr, int to)
        vector[vector[int]] scc()
cdef class scc_graph_:
    cdef scc_graph *ptr
    def __cinit__(self, int n): self.ptr = new scc_graph(n)  
    def __dealloc__(self): del self.ptr
    cpdef void add_edge(self, int fr, int to): self.ptr.add_edge(fr, to)
    cpdef vector[vector[int]] scc(self): return self.ptr.scc()
"""

import os
try:
    from atcoder import *
except:
    open('atcoder.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
g=scc_graph_(N)
for a,b in AB:
    g.add_edge(a,b)
r=g.scc()
print(len(r))
for l in r:
    print(len(l),*l)