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 argsort(arr, reverse=False, shift=20):
    N = len(arr)
    tmp=[0]*N
    for i in range(N):
        tmp[i] = (arr[i] << shift) | i
    tmp = sorted(tmp,reverse=reverse)
    out=[0]*N
    mask = (1<<shift) - 1
    for j in range(N):
        i = tmp[j] & mask
        out[j] = i
    return out

def dfs(G1,a0,seen,postorder,order):
    todo = [~a0, a0]
    while todo:
        a = todo.pop()
        if a >= 0:
            seen[a] = 1
            for b in G1[a]:
                if seen[b]: continue
                todo.append(~b)
                todo.append(b)
        else:
          if postorder[~a] == -1:
            postorder[~a] = order
            order += 1
    return seen,postorder,order
  
def dfs2(G2,v,seen):
    todo = [v]
    seen[v] = 1
    cc = [v]
    while todo:
        v = todo.pop()
        for next_v in G2[v]:
            if seen[next_v]: continue
            seen[next_v] = 1
            todo.append(next_v)
            cc.append(next_v)
    return cc,seen
  
def scc(G1,G2):
  N = len(G1)
  seen = [0]*N
  postorder=[-1]*N
  order = 0
  for i in range(N):
    if seen[i]:continue
    seen,postorder,order = dfs(G1,i,seen,postorder,order)

  seen = [0]*N
  scclist = []
  for i in argsort(postorder,reverse=True):
    if seen[i]:continue
    cc,seen = dfs2(G2,i,seen)
    scclist.append(cc)
  return scclist

def main():
  N,M = map(int,input().split())
  G1 = [[] for _ in range(N)]
  G2 = [[] for _ in range(N)]
  for i in range(M):
    a,b=map(int,input().split())
    G1[a].append(b)
    G2[b].append(a)
  scclist = scc(G1,G2)
  print(len(scclist))
  for cc in scclist:
    print(len(cc),*cc)
    
if __name__=="__main__":
  main()