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:
from operator import itemgetter
from itertools import *
from bisect import *
from collections import *
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def scc(to,ot):
    n=len(to)
    def dfs(u):
        for v in to[u]:
            if com[v]:continue
            com[v]=1
            dfs(v)
        top.append(u)

    top=[]
    com=[0]*n
    for u in range(n):
        if com[u]:continue
        com[u]=1
        dfs(u)

    def rdfs(u,k):
        for v in ot[u]:
            if com[v]!=-1:continue
            com[v]=k
            rdfs(v,k)

    com=[-1]*n
    k=0
    for u in top[::-1]:
        if com[u]!=-1:continue
        com[u]=k
        rdfs(u,k)
        k+=1

    return k,com

n,m=MI()
to=[[] for _ in range(n)]
ot=[[] for _ in range(n)]
for _ in range(m):
    u,v=MI()
    to[u].append(v)
    ot[v].append(u)
k,com=scc(to,ot)
group=[[] for _ in range(k)]
for u,g in enumerate(com):
    group[g].append(u)
    
print(k)
for uu in group:
    print(len(uu),end=" ")
    print(*uu)