Problem: 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.

Example

Input

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


Output

4
1 5
2 4 1
1 2
2 3 0

Solution (in PYTHON3):

Solution:
import sys
readline = sys.stdin.readline
#非再帰
import sys
def scc(Edge):
    N = len(Edge)
    Edgeinv = [[] for _ in range(N)]
    for vn in range(N):
        for vf in Edge[vn]:
            Edgeinv[vf].append(vn)
    
    used = [0]*N
    order = []
    for st in range(N):
        if used[st]:
            continue
        stack = [~st, st]
        while stack:
            vn = stack.pop()
            if vn >= 0:
                if used[vn]:
                    continue
                used[vn] = 1
                for vf in Edge[vn]:
                    if used[vf]:
                        continue
                    stack.append(~vf)
                    stack.append(vf)
            else:
                if used[~vn] != 2:
                    used[~vn] = 2
                    order.append(~vn)


    res = [None]*N
    used = [False]*N
    cnt = -1
    for st in order[::-1]:
        if not used[st]:
            cnt += 1
            stack = [st]
            res[st] = cnt
            used[st] = True
            while stack:
                vn = stack.pop()
                for vf in Edgeinv[vn]:
                    if not used[vf]:
                        used[vf] = True
                        res[vf] = cnt
                        stack.append(vf)
    M = cnt+1
    components = [[] for _ in range(M)]
    for i in range(N):
        components[res[i]].append(i)
    """
    tEdge = [[] for _ in range(M)]
    teset = set()
    for vn in range(N):
        tn = res[vn]
        for vf in Edge[vn]:
            tf = res[vf]
            if tn != tf and tn*M + tf not in teset:
                teset.add(tn*M + tf)
                tEdge[tn].append(tf)
    """
    return res, components


        
N, M = map(int, readline().split())
Edge = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, readline().split())
    Edge[a].append(b)

R, comp = scc(Edge)
Ans = [str(len(comp))]

for c in comp:
    Ans.append(f'{len(c)} ' + ' '.join(map(str, c)))

print('\n'.join(Ans))