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 = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = map(int, input().split())
ns = [[] for _ in range(n)]
for _ in range(m):
    u,v = map(int, input().split())
    ns[u].append(v)
def scc():
    preorder = {}
    lowlink = {}
    seen = [False]*n
    scc_queue = []
    i = 0  # Preorder counter
    ans = []
    for source in range(n):
        if seen[source]:
            continue
        queue = [source]
        while queue:
            v = queue[-1]
            if v not in preorder:
                i = i + 1
                preorder[v] = i
            done = True
            for w in ns[v]:
                if w not in preorder:
                    queue.append(w)
                    done = False
                    break
            if done:
                lowlink[v] = preorder[v]
                for w in ns[v]:
                    if seen[w]:
                        continue
                    if preorder[w] > preorder[v]:
                        lowlink[v] = min([lowlink[v], lowlink[w]])
                    else:
                        lowlink[v] = min([lowlink[v], preorder[w]])
                queue.pop()
                if lowlink[v] == preorder[v]:
                    scc = {v}
                    seen[v] = True
                    while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
                        k = scc_queue.pop()
                        scc.add(k)
                        seen[k] = True
                    ans.append(scc)
                else:
                    scc_queue.append(v)
    return ans
comp = scc()
print(len(comp))
for item in reversed(comp):
    print(len(item), " ".join(map(str, item)))