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:
# Reference: https://mathtrain.jp/kyorenketsu#:~:text=%E5%BC%B7%E9%80%A3%E7%B5%90%E6%88%90%E5%88%86%E5%88%86%E8%A7%A3%E3%81%A8,%E9%80%A3%E7%B5%90%E6%88%90%E5%88%86%EF%BC%89%E3%81%AB%E5%B1%9E%E3%81%97%E3%81%BE%E3%81%99%E3%80%82
# Reference: https://tjkendev.github.io/procon-library/python/graph/scc.html
# Strongly Connected Components
# This is made for "AtCoderLibraryPracticeContest/G-SCC"
from sys import stdin, setrecursionlimit
setrecursionlimit(10**9)
input = stdin.buffer.readline

# n = the number of nodes
# m = the number of edges
n, m = map(int, input().split())

edges = [[] for _ in range(n)]
reversed_edges = [[] for _ in range(n)]
for _ in range(m):
    i, j = map(int, input().split())
    edges[i].append(j)
    reversed_edges[j].append(i)

def scc(n, edges, reversed_edges):
    order = []
    seen = [True] * n

    def dfs(node):
        seen[node] = False
        for i in edges[node]:
            if seen[i]:
                dfs(i)
        order.append(node)

    for i in range(n):
        if seen[i]:
            dfs(i)

    groups = []
    seen = [True] * n
    for start in reversed(order):
        if seen[start]:
            ### DFS
            seen[start] = False
            todo = [start]
            group = [start]
            while len(todo) > 0:
                node = todo.pop(-1)
                for j in reversed_edges[node]:
                    if seen[j]:
                        seen[j] = False
                        todo.append(j)
                        group.append(j)
            ###
            group.reverse()
            groups.append(group)

    return groups

groups = scc(n, edges, reversed_edges)
print(len(groups))
for group in groups:
    print(len(group), ' '.join(map(str, group)))