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
input = sys.stdin.readline
n,m = map(int, input().split())
es = [[] for _ in range(n)]
for i in range(m):
    a,b=map(int, input().split())
    es[a].append(b)

# Strongly Connected Component
def scc(n_node,es): # DFSを2回行う
    esinv = [[] for _ in range(n_node)]
    for i in range(n_node):
        for e in es[i]:
            esinv[e].append(i)
    used = [False]*n_node
    dim = [len(es[i]) for i in range(n_node)]
    order = []
    for st in range(n_node): # DFS 1回目, postorderを求める
        if not used[st]:
            stack = [(st, 0)] # [(index, 既に辿ったエッジの数)]
            while stack:
                now, i = stack.pop() 
                if not i and used[now]:
                    continue
                else:
                    used[now] = True
                    if i < dim[now]: # nowから延びるエッジを辿りきってない
                        stack.append((now,i+1))
                        stack.append((es[now][i],0))
                    else: # nowから延びる全てのエッジを辿った
                        order.append(now)
    res = [-1]*n_node # 各ノードが所属するグループのidを保存
    used = [False]*n_node 
    cnt = -1 # idカウンター
    for st in order[::-1]:  # DFS 2回目, postorderの逆順から
        if not used[st]:    # 逆向き矢印を辿って通れるノードを記録していく
            cnt += 1
            stack = [st]
            res[st] = cnt
            used[st] = True
            while stack:
                now = stack.pop()
                for e in esinv[now]:
                    if not used[e]:
                        used[e] = True
                        res[e] = cnt
                        stack.append(e)
    n_group = cnt+1
    components = [[] for _ in range(n_group)]
    for i in range(n_node):
        components[res[i]].append(i)
    return components # 各グループのノード

comp=scc(n,es)
row=len(comp)
print(row)
for i in range(row):
    length = len(comp[i])
    print(length, *comp[i])