#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


class SCC{
public:
  int V,K;                      //頂点数, scc後の頂点数
  vector<vector<int> > G;       //グラフの隣接リストの表現
  vector<vector<int> >rG;       //辺の向きを逆にしたグラフ
  vector<vector<int> >DAG;      //scc後のグラフの隣接リストの表現
  vector<vector<int> >rDAG;     //scc後の辺の向きを逆にしたグラフ
  vector<int> vs;               //帰りがけ順の並び
  vector<int>used;              //すでに調べたか
  vector<int> cmp;              //属する強連結成分のトポロジカル順
  vector<vector<int> > member;  //scc後の同じグループのノードの集合
  int ok;                       //buildされているか。
  SCC(){V = K = -1;}
  SCC(int V):V(V),G(V),rG(V),used(V,0),cmp(V),ok(0){}

  void add_edge(int from,int to){
    assert(from<V && to<V);
    G[from].push_back(to);
    rG[to].push_back(from);
  }

  void dfs(int v){
    used[v]=true;
    for(int nx:G[v]) if(!used[nx]) dfs(nx);
    vs.push_back(v);
  }

  void rdfs(int v,int k){
    used[v]=true;
    cmp[v]=k;
    for(int nx:rG[v]) if(!used[nx]) rdfs(nx,k);
  }

  int build(bool makeDAG = 0){ //DAGのグラフも作りたかったらmakeDAGを1にする
    ok = true;
    used.clear(); used.resize(V,0);
    vs.clear();
    for(int v=0;v<V;v++) if(!used[v]) dfs(v);

    used.clear(); used.resize(V,0);
    int &k= K = 0;
    for(int i=vs.size()-1;i>=0;i--)if(!used[vs[i]]) rdfs(vs[i],k++);

    member.clear();
    member.resize(k);
    for(int i=0;i<V;i++) member[cmp[i]].push_back(i);

    if(makeDAG) DAG = getDAG(G), rDAG = getDAG(rG); //O(ElogE)

    return k;
  }

  bool same(int u, int v){assert(ok);return cmp[u] == cmp[v];}

private:
  vector<vector<int> > getDAG(const vector<vector<int> > &G){
    assert(K>=0);
    vector<vector<int> >res(K);
    for(int from=0;from<V;from++)
      for(int to:G[from]) if(cmp[from]!=cmp[to]) res[cmp[from]].push_back(cmp[to]);

    for(int i=0;i<K;i++){
      sort(res[i].begin(),res[i].end());
      res[i].erase(unique(res[i].begin(),res[i].end()),res[i].end());
    }
    return res;
  }
};

signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);


  int N, M;
  cin>>N>>M;

  SCC scc(N);

  for(int i=0;i<M;i++){
    int a, b;
    cin>>a>>b; a--, b--;
    scc.add_edge(a, b);
  }

  scc.build();

  for(int i=0;i<N;i++){
    int cnt = 0;
    for(int j=0;j<N;j++){
      if(scc.same(i, j)){
        if(cnt++) cout<<" ";
        cout<<j+1;
      }
    }
    cout<<endl;
  }

  return 0;
}


### Prompt

Develop a solution in cpp to the problem described below:

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>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}
//INSERT ABOVE HERE


class SCC{
public:
  int V,K;                      //頂点数, scc後の頂点数
  vector<vector<int> > G;       //グラフの隣接リストの表現
  vector<vector<int> >rG;       //辺の向きを逆にしたグラフ
  vector<vector<int> >DAG;      //scc後のグラフの隣接リストの表現
  vector<vector<int> >rDAG;     //scc後の辺の向きを逆にしたグラフ
  vector<int> vs;               //帰りがけ順の並び
  vector<int>used;              //すでに調べたか
  vector<int> cmp;              //属する強連結成分のトポロジカル順
  vector<vector<int> > member;  //scc後の同じグループのノードの集合
  int ok;                       //buildされているか。
  SCC(){V = K = -1;}
  SCC(int V):V(V),G(V),rG(V),used(V,0),cmp(V),ok(0){}

  void add_edge(int from,int to){
    assert(from<V && to<V);
    G[from].push_back(to);
    rG[to].push_back(from);
  }

  void dfs(int v){
    used[v]=true;
    for(int nx:G[v]) if(!used[nx]) dfs(nx);
    vs.push_back(v);
  }

  void rdfs(int v,int k){
    used[v]=true;
    cmp[v]=k;
    for(int nx:rG[v]) if(!used[nx]) rdfs(nx,k);
  }

  int build(bool makeDAG = 0){ //DAGのグラフも作りたかったらmakeDAGを1にする
    ok = true;
    used.clear(); used.resize(V,0);
    vs.clear();
    for(int v=0;v<V;v++) if(!used[v]) dfs(v);

    used.clear(); used.resize(V,0);
    int &k= K = 0;
    for(int i=vs.size()-1;i>=0;i--)if(!used[vs[i]]) rdfs(vs[i],k++);

    member.clear();
    member.resize(k);
    for(int i=0;i<V;i++) member[cmp[i]].push_back(i);

    if(makeDAG) DAG = getDAG(G), rDAG = getDAG(rG); //O(ElogE)

    return k;
  }

  bool same(int u, int v){assert(ok);return cmp[u] == cmp[v];}

private:
  vector<vector<int> > getDAG(const vector<vector<int> > &G){
    assert(K>=0);
    vector<vector<int> >res(K);
    for(int from=0;from<V;from++)
      for(int to:G[from]) if(cmp[from]!=cmp[to]) res[cmp[from]].push_back(cmp[to]);

    for(int i=0;i<K;i++){
      sort(res[i].begin(),res[i].end());
      res[i].erase(unique(res[i].begin(),res[i].end()),res[i].end());
    }
    return res;
  }
};

signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);


  int N, M;
  cin>>N>>M;

  SCC scc(N);

  for(int i=0;i<M;i++){
    int a, b;
    cin>>a>>b; a--, b--;
    scc.add_edge(a, b);
  }

  scc.build();

  for(int i=0;i<N;i++){
    int cnt = 0;
    for(int j=0;j<N;j++){
      if(scc.same(i, j)){
        if(cnt++) cout<<" ";
        cout<<j+1;
      }
    }
    cout<<endl;
  }

  return 0;
}


```