// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1001001001;
const ll LONGINF = 1001001001001001LL;
const ll MOD = 1000000007LL;

// 移動元と行先と辺のコストを記録する構造体
template <typename T = int>
struct Edge {
    int from, to;
    T cost;
    Edge(int s, T d = 1) : to(s), cost(d) {}
    Edge(int f, int s, T d) : from(f), to(s), cost(d) {}

    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
    bool operator>(const Edge &e) const {
        return cost > e.cost;
    }
};

template <typename T = int>
using Graph = vector< vector< Edge<T> > >;

// 強連結成分分解
// Verified: AOJ GRL_3_C (Strongly Connected Components)
// Verified: ARC030 C (有向グラフ) ← 強連結を潰したグラフの構築の検証

// これは 2 回の DFS によって実現できる。
// はじめに普通の DFS をするが、その時に帰りがけ順に頂点番号の配列を作る。
// 次に、元のグラフの逆辺のみで構成されたグラフに対して、
// 帰りがけ順が遅かったものから順に DFS を行う。
// 帰りかけが遅かった頂点ほど、 DAG の先頭の強連結成分に属しているため、
// 辺を逆向きにすると、先頭の強連結成分から外に出られなくなることを利用している。

template <typename T = int>
struct GraphSCC {
public:
    const int n;
    vector<bool> isthrough;
    vector<int> vs, cmp;
    vector< vector<int> > G, rG, H; // グラフ、逆辺グラフ、縮約後のグラフ

    GraphSCC(vector< vector< Edge<T> > > &g) :
        n(g.size()), isthrough(n, false), cmp(n, 0), G(n), rG(n) {
        for(int i=0; i<n; i++) {
            for(size_t j=0; j<g[i].size(); j++) {
                G[i].push_back(g[i][j].to);
                rG[ g[i][j].to ].push_back(i);
            }
        }
    }

    void SCC_dfsone(int cur) {
        isthrough[cur] = true;
        for(size_t i=0; i<G[cur].size(); i++) {
            if(!isthrough[G[cur][i]]) {
                SCC_dfsone(G[cur][i]);
            }
        }
        vs.push_back(cur);
    }

    void SCC_dfstwo(vector<int> &vec, int cur, int k) {
        cmp[cur] = k;
        isthrough[cur] = true;
        vec.push_back(cur);
        for(size_t i=0; i<rG[cur].size(); i++) {
            if(!isthrough[rG[cur][i]]) {
                SCC_dfstwo(vec, rG[cur][i], k);
            }
        }
    }

    // 縮約後のグループ、グループ数
    pair<vector<int>, int> scc() {
        // 1回めのDFS
        for(int i=0; i<n; i++)
            if(!isthrough[i]) SCC_dfsone(i);

        fill(isthrough.begin(), isthrough.end(), false);
        reverse(vs.begin(), vs.end());
        int k = 0; vector< vector<int> > S;

        // 2回めのDFS
        for(size_t i=0; i<vs.size(); i++) {
            if(!isthrough[vs[i]]) {
                S.push_back(vector<int>());
                SCC_dfstwo(S.back(), vs[i], k++);
            }
        }

        H.resize(k);
        fill(isthrough.begin(), isthrough.end(), false);
        for(size_t i=0; i<k; i++) {
            for(size_t j=0; j<S[i].size(); j++) {
                int v = S[i][j];
                for(size_t x=0; x<G[v].size(); x++) {
                    int u = G[v][x];
                    if(isthrough[cmp[u]] || cmp[v] == cmp[u]) continue;
                    isthrough[cmp[u]] = true;
                    H[cmp[v]].push_back(cmp[u]);
                }
            }
            for(size_t j=0; j<H[i].size(); j++) isthrough[ H[i][j] ] = false;
        }
        return make_pair(cmp, k);
    }
};


int main() {
    int N, M; cin >> N >> M;

    Graph<int> G(N);
    for(int i=0; i<M; i++) {
        int a, b; cin >> a >> b;
        a--; b--;
        G[a].emplace_back(b);
    }

    GraphSCC<> gs(G);
    auto res = gs.scc();

    int K = res.second;
    vector< vector<int> > ans(K);
    for(int i=0; i<N; i++) {
        int group = res.first[i];
        ans[group].emplace_back(i+1);
    }

    for(int i=0; i<N; i++) {
        int group = res.first[i];
        for(size_t j=0; j<ans[group].size(); j++) {
            cout << ans[group][j] << " \n"[j + 1 == ans[group].size()];
        }
    }
    return 0;
}


### Prompt

Your task is to create a Cpp solution to the following problem:

problem

There are $ N $ propositions, named $ 1, 2, \ cdots, N $, respectively. Also, $ M $ information about the propositions is given. The $ i $ th information is "$ a_i $$". Given in the form "b_i $", which means that $ a_i $ is $ b_i $. ("If" is a logical conditional and the transition law holds.) $ For each proposition $ i $ Output all propositions that have the same value as i $ in ascending order. However, proposition $ i $ and proposition $ i $ are always the same value. Proposition $ X $ and proposition $ Y $ have the same value as "$ if $ X $". It means "Y $" and "$ X $ if $ Y $".



output

On the $ i $ line, output all propositions that have the same value as the proposition $ i $, separated by blanks in ascending order. Also, output a line break at the end of each line.

Example

Input

5 2
1 2
2 1


Output

1 2
1 2
3
4
5

### Response

```cpp
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1001001001;
const ll LONGINF = 1001001001001001LL;
const ll MOD = 1000000007LL;

// 移動元と行先と辺のコストを記録する構造体
template <typename T = int>
struct Edge {
    int from, to;
    T cost;
    Edge(int s, T d = 1) : to(s), cost(d) {}
    Edge(int f, int s, T d) : from(f), to(s), cost(d) {}

    bool operator<(const Edge &e) const {
        return cost < e.cost;
    }
    bool operator>(const Edge &e) const {
        return cost > e.cost;
    }
};

template <typename T = int>
using Graph = vector< vector< Edge<T> > >;

// 強連結成分分解
// Verified: AOJ GRL_3_C (Strongly Connected Components)
// Verified: ARC030 C (有向グラフ) ← 強連結を潰したグラフの構築の検証

// これは 2 回の DFS によって実現できる。
// はじめに普通の DFS をするが、その時に帰りがけ順に頂点番号の配列を作る。
// 次に、元のグラフの逆辺のみで構成されたグラフに対して、
// 帰りがけ順が遅かったものから順に DFS を行う。
// 帰りかけが遅かった頂点ほど、 DAG の先頭の強連結成分に属しているため、
// 辺を逆向きにすると、先頭の強連結成分から外に出られなくなることを利用している。

template <typename T = int>
struct GraphSCC {
public:
    const int n;
    vector<bool> isthrough;
    vector<int> vs, cmp;
    vector< vector<int> > G, rG, H; // グラフ、逆辺グラフ、縮約後のグラフ

    GraphSCC(vector< vector< Edge<T> > > &g) :
        n(g.size()), isthrough(n, false), cmp(n, 0), G(n), rG(n) {
        for(int i=0; i<n; i++) {
            for(size_t j=0; j<g[i].size(); j++) {
                G[i].push_back(g[i][j].to);
                rG[ g[i][j].to ].push_back(i);
            }
        }
    }

    void SCC_dfsone(int cur) {
        isthrough[cur] = true;
        for(size_t i=0; i<G[cur].size(); i++) {
            if(!isthrough[G[cur][i]]) {
                SCC_dfsone(G[cur][i]);
            }
        }
        vs.push_back(cur);
    }

    void SCC_dfstwo(vector<int> &vec, int cur, int k) {
        cmp[cur] = k;
        isthrough[cur] = true;
        vec.push_back(cur);
        for(size_t i=0; i<rG[cur].size(); i++) {
            if(!isthrough[rG[cur][i]]) {
                SCC_dfstwo(vec, rG[cur][i], k);
            }
        }
    }

    // 縮約後のグループ、グループ数
    pair<vector<int>, int> scc() {
        // 1回めのDFS
        for(int i=0; i<n; i++)
            if(!isthrough[i]) SCC_dfsone(i);

        fill(isthrough.begin(), isthrough.end(), false);
        reverse(vs.begin(), vs.end());
        int k = 0; vector< vector<int> > S;

        // 2回めのDFS
        for(size_t i=0; i<vs.size(); i++) {
            if(!isthrough[vs[i]]) {
                S.push_back(vector<int>());
                SCC_dfstwo(S.back(), vs[i], k++);
            }
        }

        H.resize(k);
        fill(isthrough.begin(), isthrough.end(), false);
        for(size_t i=0; i<k; i++) {
            for(size_t j=0; j<S[i].size(); j++) {
                int v = S[i][j];
                for(size_t x=0; x<G[v].size(); x++) {
                    int u = G[v][x];
                    if(isthrough[cmp[u]] || cmp[v] == cmp[u]) continue;
                    isthrough[cmp[u]] = true;
                    H[cmp[v]].push_back(cmp[u]);
                }
            }
            for(size_t j=0; j<H[i].size(); j++) isthrough[ H[i][j] ] = false;
        }
        return make_pair(cmp, k);
    }
};


int main() {
    int N, M; cin >> N >> M;

    Graph<int> G(N);
    for(int i=0; i<M; i++) {
        int a, b; cin >> a >> b;
        a--; b--;
        G[a].emplace_back(b);
    }

    GraphSCC<> gs(G);
    auto res = gs.scc();

    int K = res.second;
    vector< vector<int> > ans(K);
    for(int i=0; i<N; i++) {
        int group = res.first[i];
        ans[group].emplace_back(i+1);
    }

    for(int i=0; i<N; i++) {
        int group = res.first[i];
        for(size_t j=0; j<ans[group].size(); j++) {
            cout << ans[group][j] << " \n"[j + 1 == ans[group].size()];
        }
    }
    return 0;
}


```