#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

//1-indexed!
class strong_components{
private:
    vector<vector<int>> v,rv,nv;
    vector<int> rs,visited,cmp,cmp_size;
    void dfs(int n){
        visited[n] = 1;
        for(auto x:v[n]) if(!visited[x]) dfs(x);
        rs.push_back(n);
    }
    void rdfs(int n,int cnt){
        visited[n] = 1;
        cmp[n] = cnt;
        for(auto x:rv[n]) if(!visited[x]) rdfs(x,cnt);
    }
public:
    strong_components(int N,vector<vector<int>>& graph){
        v = graph;
        rv = vector<vector<int>>(N+1);
        visited = cmp = cmp_size = vector<int>(N+1,0);
        for(int i=1;i<=N;i++) for(auto x:v[i]) rv[x].push_back(i);
        for(int i=1;i<=N;i++) if(!visited[i]) dfs(i);
        for(int i=1;i<=N;i++) visited[i] = 0;
        int now = 1;
        for(int i=rs.size()-1;i>=0;i--) if(!visited[rs[i]]) rdfs(rs[i],now++);
        nv = vector<vector<int>>(now+1);
        for(int i=1;i<=N;i++){
            for(auto x:v[i]){
                if(cmp[i]!=cmp[x]){
                    nv[cmp[i]].push_back(cmp[x]);
                    cmp_size[cmp[x]]++;
                }
            }
        }
    }
    int find(int n){return cmp[n];}
    bool is_same_group(int a,int b){return cmp[a]==cmp[b];}
};


int main(){
    int N,M;
    cin >> N >> M;
    vector<vector<int>> v(N+1);
    for(int i=1;i<=M;i++){
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
    }
    strong_components scc(N,v);
    vector<vector<int>> ans(N+1);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(scc.is_same_group(i,j)) ans[i].push_back(j);
        }
    }
    for(int i=1;i<=N;i++){
        int n = ans[i].size();
        for(int j=0;j<n;j++) cout << ans[i][j] << (j!=n-1? " ":"\n");
    }
}

### Prompt

Construct a cpp code solution to the problem outlined:

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>
#include <string.h>
using namespace std;

//1-indexed!
class strong_components{
private:
    vector<vector<int>> v,rv,nv;
    vector<int> rs,visited,cmp,cmp_size;
    void dfs(int n){
        visited[n] = 1;
        for(auto x:v[n]) if(!visited[x]) dfs(x);
        rs.push_back(n);
    }
    void rdfs(int n,int cnt){
        visited[n] = 1;
        cmp[n] = cnt;
        for(auto x:rv[n]) if(!visited[x]) rdfs(x,cnt);
    }
public:
    strong_components(int N,vector<vector<int>>& graph){
        v = graph;
        rv = vector<vector<int>>(N+1);
        visited = cmp = cmp_size = vector<int>(N+1,0);
        for(int i=1;i<=N;i++) for(auto x:v[i]) rv[x].push_back(i);
        for(int i=1;i<=N;i++) if(!visited[i]) dfs(i);
        for(int i=1;i<=N;i++) visited[i] = 0;
        int now = 1;
        for(int i=rs.size()-1;i>=0;i--) if(!visited[rs[i]]) rdfs(rs[i],now++);
        nv = vector<vector<int>>(now+1);
        for(int i=1;i<=N;i++){
            for(auto x:v[i]){
                if(cmp[i]!=cmp[x]){
                    nv[cmp[i]].push_back(cmp[x]);
                    cmp_size[cmp[x]]++;
                }
            }
        }
    }
    int find(int n){return cmp[n];}
    bool is_same_group(int a,int b){return cmp[a]==cmp[b];}
};


int main(){
    int N,M;
    cin >> N >> M;
    vector<vector<int>> v(N+1);
    for(int i=1;i<=M;i++){
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
    }
    strong_components scc(N,v);
    vector<vector<int>> ans(N+1);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if(scc.is_same_group(i,j)) ans[i].push_back(j);
        }
    }
    for(int i=1;i<=N;i++){
        int n = ans[i].size();
        for(int j=0;j<n;j++) cout << ans[i][j] << (j!=n-1? " ":"\n");
    }
}

```