#include<iostream>
#include<vector>
using namespace std;
vector<vector<int> > g,rg;
vector<int> vs,used,cmp;

void dfs(int v){
    used[v] = 1;
    for(int i = 0; i < g[v].size(); i++){
        if(!used[g[v][i]])dfs(g[v][i]);
    }
    vs.push_back(v);
}

void rdfs(int v, int k){
    used[v] = 1;
    cmp[v] = k;
    for(int i = 0; i < rg[v].size(); i++){
        if(!used[rg[v][i]])rdfs(rg[v][i],k);
    }
}

int main(){
    int n,m;
    cin >> n >> m;
    g = rg = vector<vector<int> >(n);
    used = cmp = vector<int>(n,0);
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        a--,b--;
        g[a].push_back(b);
        rg[b].push_back(a);
    }
    for(int v = 0; v < n; v++){
        if(!used[v])dfs(v);
    }
    used = vector<int>(n,0);
    int k = 0;
    for(int i = vs.size()-1; i >= 0; i--){
        if(!used[vs[i]])rdfs(vs[i],k++);
    }
    for(int i = 0; i < n; i++){
        int num = cmp[i];
        vector<int> ans;
        for(int j = 0; j < n; j++){
            if(cmp[j] == num)ans.push_back(j);
        }
        for(int j = 0; j < ans.size(); j++){
            if(j)cout << " ";
            cout << ans[j]+1;
        }
        cout << endl;
    }
}

### Prompt

Please create a solution in cpp 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<iostream>
#include<vector>
using namespace std;
vector<vector<int> > g,rg;
vector<int> vs,used,cmp;

void dfs(int v){
    used[v] = 1;
    for(int i = 0; i < g[v].size(); i++){
        if(!used[g[v][i]])dfs(g[v][i]);
    }
    vs.push_back(v);
}

void rdfs(int v, int k){
    used[v] = 1;
    cmp[v] = k;
    for(int i = 0; i < rg[v].size(); i++){
        if(!used[rg[v][i]])rdfs(rg[v][i],k);
    }
}

int main(){
    int n,m;
    cin >> n >> m;
    g = rg = vector<vector<int> >(n);
    used = cmp = vector<int>(n,0);
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        a--,b--;
        g[a].push_back(b);
        rg[b].push_back(a);
    }
    for(int v = 0; v < n; v++){
        if(!used[v])dfs(v);
    }
    used = vector<int>(n,0);
    int k = 0;
    for(int i = vs.size()-1; i >= 0; i--){
        if(!used[vs[i]])rdfs(vs[i],k++);
    }
    for(int i = 0; i < n; i++){
        int num = cmp[i];
        vector<int> ans;
        for(int j = 0; j < n; j++){
            if(cmp[j] == num)ans.push_back(j);
        }
        for(int j = 0; j < ans.size(); j++){
            if(j)cout << " ";
            cout << ans[j]+1;
        }
        cout << endl;
    }
}

```