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:
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())
  if a == b:continue
  G1[a].append(b)
  G2[b].append(a)

def dfs(a0):
    global 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
  
def dfs2(v):
    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 = [0]*N
postorder=[-1]*N
order = 0
for i in range(N):
  if seen[i]:continue
  dfs(i)

seen = [0]*N
scc = []
for i,_ in sorted(enumerate(postorder),key=lambda x:x[1],reverse=True):
  if seen[i]:continue
  cc = dfs2(i)
  scc.append(cc)
  
print(len(scc))
for cc in scc:
  print(len(cc),*cc)