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:
# Date [ 2020-09-10 00:44:35 ]
# Problem [ g.py ]
# Author Koki_tkg

# ERROR:: segmentation fault (core dumped)
# メモリ不足？再帰上限関連？
class csr:
    def __init__(self, n, edges):
        from copy import deepcopy
        self.start = [0] * (n + 1)
        self.elist = [[] for _ in range(len(edges))]
        for e in edges:
            self.start[e[0] + 1] += 1
        for i in range(1, n + 1):
            self.start[i] += self.start[i - 1]
        counter = deepcopy(self.start)
        for e in edges:
            self.elist[counter[e[0]]] = e[1]; counter[e[0]] += 1

class scc_graph:
    '''
    Reference:
    R. Tarjan,
    Depth-First Search and Linear Graph Algorithms
    '''
    # private
    edges = []
    
    # public
    def __init__(self, n: int): self._n = n
    
    def num_vertices(self): return self._n

    def add_edge(self, _from: int, _to: int): self.edges.append((_from, [_to]))
    
    def scc_ids(self):
        g = csr(self._n, self.edges)
        self.now_ord = 0; self.group_num = 0
        visited = []; low = [0] * self._n; ord = [-1] * self._n; ids = [0] * self._n
        
        def dfs(s, v):
            low[v] = ord[v] = self.now_ord; self.now_ord += 1
            visited.append(v)
            for i in range(g.start[v], g.start[v + 1]):
                to = g.elist[i][0]
                if ord[to] == -1:
                    s(s, to)
                    low[v] = min(low[v], low[to])
                else:
                    low[v] = min(low[v], ord[to])
            if low[v] == ord[v]:
                while True:
                    u = visited.pop()
                    ord[u] = self._n
                    ids[u] = self.group_num
                    if u == v: break
                self.group_num += 1

        for i in range(self._n):
            if ord[i] == -1: dfs(dfs, i)
        for i in range(self._n):
            ids[i] = self.group_num - 1 - ids[i]
        return (self.group_num, ids)
        
    def scc(self):
        ids = self.scc_ids()
        group_num = ids[0]
        counts = [0] * group_num
        for x in ids[1]: counts[x] += 1
        groups = [[] for _ in range(group_num)]
        for i in range(self._n):
            groups[ids[1][i]].append(i)
        return groups

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def Main():
    n, m = read_ints()
    
    scc = scc_graph(n)
    for _ in range(m):
        a, b = read_ints()
        scc.add_edge(a, b)
    ans = scc.scc()

    print(len(ans))
    for v in ans:
        print(len(v), ' '.join(map(str, v[::-1])))

if __name__ == '__main__':
    Main()