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 SCC_Tarjan(g):
    def dfs(v):
        nonlocal idx
        pre[v] = low[v] = idx
        idx += 1
        S.append(v)
        #onS[v] = 1
        for c in g[v]:
            if pre[c] == -1: 
                dfs(c)
                low[v] = min(low[v], low[c])
            #elif onS[c]:
            else:
                low[v] = min(low[v], pre[c])

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


    n = len(g)
    pre = [-1]*n # 負なら未処理、[0,n) ならpre-order, n ならvisited
    low = [0]*n
    onS = [0]*n
    idx = 0
    S = []
    scc = []
    for i in range(n):
        if pre[i] == -1:
            dfs(i)
    
    #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))