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 collections import deque

class Graph():  #directed
    def __init__(self, n, edge):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.rev = [[] for _ in range(n)]
        self.deg = [0 for _ in range(n)]
        for e in edge:
            self.graph[e[0]].append(e[1])
            self.rev[e[1]].append(e[0])
            self.deg[e[1]] += 1

    def strongry_connected(self):
        group = [None for _ in range(self.n)]
        used = [0 for _ in range(self.n)]
        order = []
        for s in range(self.n):
            if not used[s]:
                stack = [s]
                used[s] = 1
                while stack:
                    node = stack.pop()
                    movable = False
                    for adj in self.graph[node]:
                        if not used[adj]:
                            movable = True
                            used[adj] = 1
                            stack.append(node)
                            stack.append(adj)
                            break
                    if not movable:
                        order.append(node)
        used = [0 for _ in range(self.n)]
        count = 0
        for s in order[::-1]:
            if not used[s]:
                stack = [s]
                group[s] = count
                while stack:
                    node = stack.pop()
                    used[node] = 1
                    for adj in self.rev[node]:
                        if not used[adj]:
                            group[adj] = count
                            stack.append(adj)
                count += 1
        return group, count

    def topological_sort(self):
        res = [i for i in range(self.n) if self.deg[i] == 0]
        queue = deque(res)
        while queue:
            node = queue.popleft()
            for adj in self.graph[node]:
                self.deg[adj] -= 1
                if self.deg[adj] == 0:
                    queue.append(adj)
                    res.append(adj)
        return res

def simplify(edge):
    res = []
    for e in edge:
        if e[0] == e[1]:
            continue
        res.append(e)
    return tuple(set(res))

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]

edge = simplify(edge)

g = Graph(N, edge)
group, count = g.strongry_connected() #node_to_group
group_to_node = [[] for _ in range(count)]

for i in range(N):
    group_to_node[group[i]].append(i)

new_edge = []

for a, b in edge:
    new_edge.append((group[a], group[b]))

new_edge = simplify(new_edge)

new_g = Graph(count, new_edge)
ts = new_g.topological_sort()

res = [[] for _ in range(count)]

for i in range(count):
    res[i].append(len(group_to_node[ts[i]]))
    res[i].extend(group_to_node[ts[i]])

print(count)
print('\n'.join(map(lambda x: ' '.join(map(str, x)), res)))