#include <bits/stdc++.h>

using namespace std;

using i64 = long;

const i64 MOD = 1e9 + 7;
const i64 INF = 1e18 + 7;


vector<int> scc(vector<vector<int>>& edges){
    int n = edges.size();
    vector<vector<int>> rev(n);

    for(int i = 0; i < n; ++i)
        for(auto& x : edges[i])
            rev[x].emplace_back(i);

    vector<i64> dfs_num(n, -1);
    vector<i64> flag(n, 0);
    int num = 0;
    function<void(int)> dfs = [&](int pos){
        flag[pos] = 1;
        for(auto& xx : edges[pos])
            if(!flag[xx]){
                dfs(xx);
        }
        dfs_num[pos] = num++;
    };

    for(int i = 0; i < n; ++i)
        if(!flag[i])
            dfs(i);

    vector<int> dfs_inv(n);
    for(int i = 0; i < n; ++i)
        dfs_inv[n - 1 - dfs_num[i]] = i;

    num = 0;

    vector<int> scc_vec(n, -1);

    function<void(int)> rdfs = [&](int pos){
        scc_vec[pos] = num;
        for(auto t : rev[pos])
            if(scc_vec[t] == -1)
                rdfs(t);
    };

    for(int i = 0; i < n; ++i)
        if(scc_vec[dfs_inv[i]] == -1){
            rdfs(dfs_inv[i]);
            ++num;
        }

    return scc_vec;
}


signed main(){
    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m);
    vector<vector<int>> edges(n);
    for(int i = 0; i < m; ++i){
        cin >> a[i] >> b[i];
        edges[--a[i]].emplace_back(--b[i]);
    }

    auto ret = scc(edges);
    for(int i = 0; i < n; ++i){
        bool fl = false;
        for(int j = 0; j < n; ++j)
            if(ret[i] == ret[j]){
                if(fl)
                    cout << " ";
                cout << j + 1;
                fl = true;
            }
        cout << endl;
    }
}


### Prompt

Create a solution in CPP for 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;

using i64 = long;

const i64 MOD = 1e9 + 7;
const i64 INF = 1e18 + 7;


vector<int> scc(vector<vector<int>>& edges){
    int n = edges.size();
    vector<vector<int>> rev(n);

    for(int i = 0; i < n; ++i)
        for(auto& x : edges[i])
            rev[x].emplace_back(i);

    vector<i64> dfs_num(n, -1);
    vector<i64> flag(n, 0);
    int num = 0;
    function<void(int)> dfs = [&](int pos){
        flag[pos] = 1;
        for(auto& xx : edges[pos])
            if(!flag[xx]){
                dfs(xx);
        }
        dfs_num[pos] = num++;
    };

    for(int i = 0; i < n; ++i)
        if(!flag[i])
            dfs(i);

    vector<int> dfs_inv(n);
    for(int i = 0; i < n; ++i)
        dfs_inv[n - 1 - dfs_num[i]] = i;

    num = 0;

    vector<int> scc_vec(n, -1);

    function<void(int)> rdfs = [&](int pos){
        scc_vec[pos] = num;
        for(auto t : rev[pos])
            if(scc_vec[t] == -1)
                rdfs(t);
    };

    for(int i = 0; i < n; ++i)
        if(scc_vec[dfs_inv[i]] == -1){
            rdfs(dfs_inv[i]);
            ++num;
        }

    return scc_vec;
}


signed main(){
    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m);
    vector<vector<int>> edges(n);
    for(int i = 0; i < m; ++i){
        cin >> a[i] >> b[i];
        edges[--a[i]].emplace_back(--b[i]);
    }

    auto ret = scc(edges);
    for(int i = 0; i < n; ++i){
        bool fl = false;
        for(int j = 0; j < n; ++j)
            if(ret[i] == ret[j]){
                if(fl)
                    cout << " ";
                cout << j + 1;
                fl = true;
            }
        cout << endl;
    }
}


```