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