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------

import copy
import sys
sys.setrecursionlimit(1000000)

class csr:
  # start 頂点iまでの頂点が、矢元として現れた回数
  # elist 矢先のリストを矢元の昇順にしたもの
  def __init__(s, n, edges):
    s.start = [0] * (n + 1)
    s.elist = [[] for _ in range(len(edges))]
    for e in edges:
      s.start[e.frm + 1] += 1
    for i in range(1, n + 1):
      s.start[i] += s.start[i - 1]
    counter = copy.deepcopy(s.start)
    for e in edges:
      s.elist[counter[e.frm]] = e.to
      counter[e.frm] += 1

class scc_graph:
  # n 頂点数
  def __init__(s, n): 
    s._n = n
    s.edges = []
  def num_vertices(s): return s._n
  # 辺を追加 frm 矢元 to 矢先
  # O(1)
  def add_edge(s, frm, to): s.edges.append(s.edge(frm, to))

  # グループの個数と各頂点のグループidを返す
  def scc_ids(s):
    g = csr(s._n, s.edges)
    now_ord = group_num = 0
    visited = []
    low = [0] * s._n
    ord = [-1] * s._n
    ids = [0] * s._n
    # 再帰関数 
    def dfs(self, v, now_ord, group_num):
      low[v] = ord[v] = now_ord
      now_ord += 1
      visited.append(v)
      for i in range(g.start[v], g.start[v + 1]):
        to = g.elist[i]
        if ord[to] == -1:
          now_ord, group_num = self(self, to, now_ord, group_num)
          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] = s._n
          ids[u] = group_num
          if u == v: break
        group_num += 1
      return now_ord, group_num

    for i in range(s._n):
      if ord[i] == -1: now_ord, group_num = dfs(dfs, i, now_ord, group_num)
    for i in range(s._n):
      ids[i] = group_num - 1 - ids[i]
    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

  class edge:
    def __init__(s, frm, to):
      s.frm = frm
      s.to = to


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

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()