
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>
#include <set>
#include <unordered_set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>
#include <locale>
#include <random>
#include <type_traits>

using namespace std;

#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

using LL = long long;

//------------------------------------------
//------------------------------------------

template<class T>
struct Edge {
    int from, to;
    T cost;

    Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}

    operator int() const { return to; }
};

template<class T>
using Edges = vector<Edge<T>>;
template<class T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template<class T>
using DistMatrix = vector<vector<T>>;

template<typename G>
struct StrongConnectedComponents {

    /// @bried graph SCCする元グラフ
    const G &graph;
    int V;

    /// @brief graph SCC用の内部グラフ
    UnWeightedGraph go_g, rv_g;

    /// @brief comp comp[v] = vの所属するSCCの番号 トポロジカル順
    vector<int> comp;

    /// @brief dfs用
    vector<bool> used;

    /// @brief dfsの帰りがけ順
    vector<int> order;

    StrongConnectedComponents(G &graph) :
            graph(graph), V(graph.size()), go_g(V), rv_g(V), comp(V, -1), used(V, false) {
        for (int i = 0; i < V; i++) {
            for (auto e: graph[i]) {
                go_g[i].emplace_back((int) e);
                rv_g[(int) e].emplace_back(i);
            }
        }
    }

    /// @brief 頂点vの所属するSCCのIDのを返す
    int operator[](int v) {
        return comp[v];
    }

    void dfs(int v) {
        if (used[v])return;
        used[v] = true;
        for (auto to: go_g[v]) dfs(to);
        order.emplace_back(v);
    }

    void rdfs(int v, int cnt) {
        if (comp[v] != -1) return;
        comp[v] = cnt;
        for (auto to: rv_g[v]) rdfs(to, cnt);
    }

    vector<int> get_comp() const {
        return comp;
    }

    /// @param gt 参照で空グラフを与える gt[SCCID]が繋がる他の頂点
    void build(UnWeightedGraph &gt) {
        for (int i = 0; i < V; i++) dfs(i);
        reverse(order.begin(), order.end());
        int cnt = 0;
        for (auto v: order) if (comp[v] == -1) rdfs(v, cnt), cnt++;
        gt.resize(cnt);
        for (int i = 0; i < V; i++) {
            for (auto &to: graph[i]) {
                int x = comp[i];
                int y = comp[(int) to];
                if (x == y) continue;
                gt[x].push_back(y);
            }
        }
    }

};

int main() {

    int N, M;
    cin >> N >> M;

    UnWeightedGraph graph(N), gt;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].push_back(b);
    }

    StrongConnectedComponents<UnWeightedGraph > scc(graph);
    scc.build(gt);

    for (int i = 0; i < N; i++) {
        vector<int> ans;
        for (int j = 0; j < N; j++) {
            if (scc[i] == scc[j]) {
                ans.push_back(j + 1);
            }
        }
        for (int j = 0; j < ans.size(); j++) {
            if(j == ans.size() - 1) cout << ans[j] << endl;
            else cout << ans[j] << " ";
        }
    }

    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

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>
#include <set>
#include <unordered_set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>
#include <locale>
#include <random>
#include <type_traits>

using namespace std;

#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

using LL = long long;

//------------------------------------------
//------------------------------------------

template<class T>
struct Edge {
    int from, to;
    T cost;

    Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}

    operator int() const { return to; }
};

template<class T>
using Edges = vector<Edge<T>>;
template<class T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template<class T>
using DistMatrix = vector<vector<T>>;

template<typename G>
struct StrongConnectedComponents {

    /// @bried graph SCCする元グラフ
    const G &graph;
    int V;

    /// @brief graph SCC用の内部グラフ
    UnWeightedGraph go_g, rv_g;

    /// @brief comp comp[v] = vの所属するSCCの番号 トポロジカル順
    vector<int> comp;

    /// @brief dfs用
    vector<bool> used;

    /// @brief dfsの帰りがけ順
    vector<int> order;

    StrongConnectedComponents(G &graph) :
            graph(graph), V(graph.size()), go_g(V), rv_g(V), comp(V, -1), used(V, false) {
        for (int i = 0; i < V; i++) {
            for (auto e: graph[i]) {
                go_g[i].emplace_back((int) e);
                rv_g[(int) e].emplace_back(i);
            }
        }
    }

    /// @brief 頂点vの所属するSCCのIDのを返す
    int operator[](int v) {
        return comp[v];
    }

    void dfs(int v) {
        if (used[v])return;
        used[v] = true;
        for (auto to: go_g[v]) dfs(to);
        order.emplace_back(v);
    }

    void rdfs(int v, int cnt) {
        if (comp[v] != -1) return;
        comp[v] = cnt;
        for (auto to: rv_g[v]) rdfs(to, cnt);
    }

    vector<int> get_comp() const {
        return comp;
    }

    /// @param gt 参照で空グラフを与える gt[SCCID]が繋がる他の頂点
    void build(UnWeightedGraph &gt) {
        for (int i = 0; i < V; i++) dfs(i);
        reverse(order.begin(), order.end());
        int cnt = 0;
        for (auto v: order) if (comp[v] == -1) rdfs(v, cnt), cnt++;
        gt.resize(cnt);
        for (int i = 0; i < V; i++) {
            for (auto &to: graph[i]) {
                int x = comp[i];
                int y = comp[(int) to];
                if (x == y) continue;
                gt[x].push_back(y);
            }
        }
    }

};

int main() {

    int N, M;
    cin >> N >> M;

    UnWeightedGraph graph(N), gt;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        graph[a].push_back(b);
    }

    StrongConnectedComponents<UnWeightedGraph > scc(graph);
    scc.build(gt);

    for (int i = 0; i < N; i++) {
        vector<int> ans;
        for (int j = 0; j < N; j++) {
            if (scc[i] == scc[j]) {
                ans.push_back(j + 1);
            }
        }
        for (int j = 0; j < ans.size(); j++) {
            if(j == ans.size() - 1) cout << ans[j] << endl;
            else cout << ans[j] << " ";
        }
    }

    return 0;
}




































```