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:
#-------最強ライブラリSCC(Python) ver25252------
class scc_graph:
  # n 頂点数
  def __init__(s, n): 
    s._n = n
    s.g = [[] for _ in range(n)]
    s.rg = [[] for _ in range(n)]
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): 
    s.g[frm].append(to)
    s.rg[to].append(frm)

  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    def dfs(v):
      stack = [v]
      while stack:
        t = stack.pop()
        vis[t] = True
        for i in s.g[t]:
          if not vis[i]:
            stack.append(t)
            stack.append(i)
            break
        else:
          vs.append(t)

    def rdfs(v, n):
      stack = [v]
      vis[v] = True
      ids[v] = n
      while stack:
        t = stack.pop()
        vis[t] = True
        for i in s.rg[t]:
          if not vis[i]:
            ids[i] = n
            stack.append(i)

    vis = [False] * s._n 
    vs = []
    ids = [-1] * s._n
    for i in range(s._n):
      if not vis[i]:
        dfs(i)
    group_num = 0
    vis = [False] * s._n 
    for i in vs[::-1]:
      if not vis[i]:
        rdfs(i, group_num)
        group_num += 1
    return group_num, ids 

  # 強連結成分となっている頂点のリストのリスト トポロジカルソート済み
  # O(n + m)
  def scc(s):
    ids = s.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(s._n):
      groups[ids[1][i]].append(i)
    return groups

#-------最強ライブラリここまで------

import sys
def main():
  input = sys.stdin.readline

  n, m = list(map(int, input().split()))
  ab = [list(map(int, input().split())) for _ in range(m)]

  g = scc_graph(n)

  for i in range(m):
    u, v = ab[i]
    g.add_edge(u, v)

  scc = g.scc()

  print(len(scc))

  for v in scc:
    print(len(v), end = " ")
    for x in v:
      print(x, end = " ")
    print("")

main()