
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> P;

struct StronglyConnectedComponents {
    int N;
    vector<vector<int> > g, gr, g2i;
    vector<bool> visited;
    vector<int> i2g;
    vector<P> edges;
    stack<int> st;

    StronglyConnectedComponents(){};
    StronglyConnectedComponents(int n){init(n);}
    void init(int n){
        N = n;
        g.clear();
        g.resize(n);
        gr.clear();
        gr.resize(n);
        edges.clear();
        visited.resize(n);
        i2g.resize(n);
    }
    void add_edge(int u, int v) {
        g[u].push_back(v);
        gr[v].push_back(u);
        edges.push_back(P(u, v));
    }

    void dfs(int x) {
        if (visited[x]) return;
        visited[x] = true;
        for (int i : g[x]) dfs(i);
        st.push(x);
    }

    void rdfs(int x, int k) {
        if (i2g[x] != -1) return;
        i2g[x] = k;
        for (int i : gr[x]) rdfs(i, k);
    }

    void build() {
        fill(visited.begin(), visited.end(), false);
        fill(i2g.begin(), i2g.end(), -1);
        for (int i = 0; i < N; i++) dfs(i);
        int p = 0;
        while (!st.empty()) {
            int v = st.top();
            st.pop();
            if (i2g[v] == -1) {
                rdfs(v, p);
                p++;
            }
        }
        g2i.clear();
        g2i.resize(p);
        for(int i=0;i<N;i++){
            g2i[i2g[i]].push_back(i);
        }
    }
};

int main(){
    int n, m;
    cin >> n >> m;
    StronglyConnectedComponents G(n);
    for(int i=0;i<m;i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        G.add_edge(a,b);
    }
    G.build();
    for(int i=0;i<n;i++){
        int id = G.i2g[i];
        for(int j=0;j<int(G.g2i[id].size());j++){
            cout << G.g2i[id][j]+1 << " \n"[j==int(G.g2i[id].size())-1];
        }
    }
}

### Prompt

In cpp, your task is to solve 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 <bits/stdc++.h>
using namespace std;

typedef pair<int, int> P;

struct StronglyConnectedComponents {
    int N;
    vector<vector<int> > g, gr, g2i;
    vector<bool> visited;
    vector<int> i2g;
    vector<P> edges;
    stack<int> st;

    StronglyConnectedComponents(){};
    StronglyConnectedComponents(int n){init(n);}
    void init(int n){
        N = n;
        g.clear();
        g.resize(n);
        gr.clear();
        gr.resize(n);
        edges.clear();
        visited.resize(n);
        i2g.resize(n);
    }
    void add_edge(int u, int v) {
        g[u].push_back(v);
        gr[v].push_back(u);
        edges.push_back(P(u, v));
    }

    void dfs(int x) {
        if (visited[x]) return;
        visited[x] = true;
        for (int i : g[x]) dfs(i);
        st.push(x);
    }

    void rdfs(int x, int k) {
        if (i2g[x] != -1) return;
        i2g[x] = k;
        for (int i : gr[x]) rdfs(i, k);
    }

    void build() {
        fill(visited.begin(), visited.end(), false);
        fill(i2g.begin(), i2g.end(), -1);
        for (int i = 0; i < N; i++) dfs(i);
        int p = 0;
        while (!st.empty()) {
            int v = st.top();
            st.pop();
            if (i2g[v] == -1) {
                rdfs(v, p);
                p++;
            }
        }
        g2i.clear();
        g2i.resize(p);
        for(int i=0;i<N;i++){
            g2i[i2g[i]].push_back(i);
        }
    }
};

int main(){
    int n, m;
    cin >> n >> m;
    StronglyConnectedComponents G(n);
    for(int i=0;i<m;i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        G.add_edge(a,b);
    }
    G.build();
    for(int i=0;i<n;i++){
        int id = G.i2g[i];
        for(int j=0;j<int(G.g2i[id].size());j++){
            cout << G.g2i[id][j]+1 << " \n"[j==int(G.g2i[id].size())-1];
        }
    }
}

```