#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long

struct SCC{
  vector< vector<int> > G; //グラフの隣接リスト
  vector< vector<int> > rG; //辺の向きを逆にしたグラフ
  vector<int> vs; //帰りがけ順の並び
  vector<bool> visited; //既に調べたか
  vector<int> cmp; //トポロジカル順序 値が等しければ強連結成分

  void init(int _V){
    int V = _V;
    G.resize(V);
    rG.resize(V);
    visited.resize(V);
    cmp.resize(V);
  }

  void dfs(int v){
    visited[v] = true;
    for(int i = 0; i < G[v].size(); i++){
      if(!visited[G[v][i]]) dfs(G[v][i]);
    }
    vs.push_back(v);
  }

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

  int scc(int V){
    fill(visited.begin(),visited.begin()+V,false);
    for(int v = 0; v < V; v++){
      if(!visited[v]) dfs(v);
    }

    fill(visited.begin(),visited.begin()+V,false);
    int k = 0;
    for(int i = vs.size()-1; i >= 0; i--){
      if(!visited[vs[i]]) rdfs(vs[i],k++);
    }
    return k;
  }

}scc;

signed main(){

  int n,m; cin >> n >> m;
  scc.init(n);
  for(int i = 0; i < m; i++){
    int a,b; cin >> a >> b;
    a--,b--;
    scc.G[a].push_back(b);
    scc.rG[b].push_back(a);
  }
  scc.scc(n);

  for(int i = 0; i < n; i++){
    bool judge = true;
    for(int j = 0; j < n; j++){
      if(scc.cmp[i] == scc.cmp[j]){
        if(!judge) cout << " ";
        cout << j+1;
        judge = false;
      }
    }
    if(judge) cout << i+1;
    cout << endl;
  }

  return 0;
}


### 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;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long

struct SCC{
  vector< vector<int> > G; //グラフの隣接リスト
  vector< vector<int> > rG; //辺の向きを逆にしたグラフ
  vector<int> vs; //帰りがけ順の並び
  vector<bool> visited; //既に調べたか
  vector<int> cmp; //トポロジカル順序 値が等しければ強連結成分

  void init(int _V){
    int V = _V;
    G.resize(V);
    rG.resize(V);
    visited.resize(V);
    cmp.resize(V);
  }

  void dfs(int v){
    visited[v] = true;
    for(int i = 0; i < G[v].size(); i++){
      if(!visited[G[v][i]]) dfs(G[v][i]);
    }
    vs.push_back(v);
  }

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

  int scc(int V){
    fill(visited.begin(),visited.begin()+V,false);
    for(int v = 0; v < V; v++){
      if(!visited[v]) dfs(v);
    }

    fill(visited.begin(),visited.begin()+V,false);
    int k = 0;
    for(int i = vs.size()-1; i >= 0; i--){
      if(!visited[vs[i]]) rdfs(vs[i],k++);
    }
    return k;
  }

}scc;

signed main(){

  int n,m; cin >> n >> m;
  scc.init(n);
  for(int i = 0; i < m; i++){
    int a,b; cin >> a >> b;
    a--,b--;
    scc.G[a].push_back(b);
    scc.rG[b].push_back(a);
  }
  scc.scc(n);

  for(int i = 0; i < n; i++){
    bool judge = true;
    for(int j = 0; j < n; j++){
      if(scc.cmp[i] == scc.cmp[j]){
        if(!judge) cout << " ";
        cout << j+1;
        judge = false;
      }
    }
    if(judge) cout << i+1;
    cout << endl;
  }

  return 0;
}


```