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 = sys.stdin.buffer.readline


class StronglyConnectedComponents:
    """与えられた有向グラフに対して強連結成分分解する。構築O(N)
    label: 分解されたグラフの個数
    group: 強連結成分のグループ分け番号
    """
    def __init__(self, graph):
        self.n = len(graph)
        self.graph = graph
        self.out_degree = [len(self.graph[i]) for i in range(self.n)]
        self.label = 0
        self.group = [-1] * self.n

        # 逆辺を用いたグラフ(rev_graph)の構築
        self.rev_graph = [[] for i in range(self.n)]
        for a in range(self.n):
            for b in self.graph[a]:
                self.rev_graph[b].append(a)

        # graph上での帰りがけ順(post_order)の構築
        self.post_order = []
        self.used = [False] * self.n
        for v in range(self.n):
            if not self.used[v]:
                self._dfs(v)

        # 帰りがけ順の逆順で走査し、
        # 未訪問かつrev_graph上でたどり着ける頂点は強連結である。
        for v in reversed(self.post_order):
            if self.group[v] == -1:
                self._rev_dfs(v, self.label)
                self.label += 1

    def _dfs(self, v):
        st = [v, 0]
        while st:
            v, ind = st[-2], st[-1]
            if not ind and self.used[v]:
                st.pop()
                st.pop()
            else:
                self.used[v] = True
                if ind < self.out_degree[v]:
                    st[-1] += 1
                    st.append(self.graph[v][ind])
                    st.append(0)
                else:
                    st.pop()
                    self.post_order.append(st.pop())

    def _rev_dfs(self, v, label):
        st = [v]
        self.group[v] = label
        while st:
            v = st.pop()
            for nxt_v in self.rev_graph[v]:
                if self.group[nxt_v] >= 0:
                    continue
                st.append(nxt_v)
                self.group[nxt_v] = label

    def construct(self):
        """縮約グラフ(red_graph)と縮約された頂点が含む元の頂点(red_comps)を
        求める。O(N)
        """
        self.red_graph = [set() for i in range(self.label)]
        self.red_comps = [[] for i in range(self.label)]

        for v in range(self.n):
            lb = self.group[v]
            for nxt_v in self.graph[v]:
                nxt_lb = self.group[nxt_v]
                if lb == nxt_lb:
                    continue
                self.red_graph[lb].add(nxt_lb)
            self.red_comps[lb].append(v)

        return self.red_graph, self.red_comps

    def tp_sort(self):
        """縮約グラフのトポロジカル順を求める。O(N)"""
        red_n = len(self.red_graph)
        indegree = [0] * red_n
        for v in range(red_n):
            for nxt_v in self.red_graph[v]:
                indegree[nxt_v] += 1

        # 入次数 = 0、つまり入力の無い頂点を初期値状態とする。
        tp_order = [i for i in range(red_n) if indegree[i] == 0]
        st = tp_order[:]
        while st:
            v = st.pop()
            for nxt_v in self.red_graph[v]:
                indegree[nxt_v] -= 1
                if indegree[nxt_v] == 0:
                    st.append(nxt_v)
                    tp_order.append(nxt_v)
        return tp_order


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


graph = [[] for i in range(n)]
for u, v in edges:
    graph[u].append(v)

scc = StronglyConnectedComponents(graph)
_, red_comps = scc.construct()
tp = scc.tp_sort()

print(len(red_comps))
for v in tp:
    print(len(red_comps[v]), *red_comps[v])