/* monkukui 競技プログラミング用のテンプレート  (ここから) */
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
using ll = long long int;
using lnt = long long int;
using graph = vector<vector<int>>;
using wgraph = vector<vector<pair<int, long long int>>>;
long long int INF = 1001001001001001LL;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;
long long int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
long long int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
inline void yes(){ cout << "yes" << endl; }
inline void Yes(){ cout << "Yes" << endl; }
inline void YES(){ cout << "YES" << endl; }
inline void no(){ cout << "no" << endl; }
inline void No(){ cout << "No" << endl; }
inline void NO(){ cout << "NO" << endl; }
inline void possible(){ cout << "possible" << endl; }
inline void Possible(){ cout << "Possible" << endl; }
inline void POSSIBLE(){ cout << "POSSIBLE" << endl; }
inline void impossible(){ cout << "impossible" << endl; }
inline void Impossible(){ cout << "Impossible" << endl; }
inline void IMPOSSIBLE(){ cout << "IMPOSSIBLE" << endl; }

#define rep(i,n) for(long long int i = 0; i < (n); i++)
#define rrep(i,n) for(long long int i = 1; i <= (n); i++)
#define drep(i,n) for(long long int i = (n)-1; i >= 0; i--)
#define srep(i,s,t) for(long long int i = s; i < t; i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back

/* monkukui 競技プログラミング用のテンプレート (ここまで)*/


struct StronglyConnectedComponents {
public:
  const int n;
  vector<bool> isthrough;
  vector<int> vs, cmp;
  vector< vector<int> > G, rG, H; // グラフ、逆辺グラフ、縮約後のグラフ

  StronglyConnectedComponents(vector<vector<int>> &g) :
    n(g.size()), isthrough(n, false), cmp(n, 0), G(n), rG(n) {
    for(int i = 0; i < n; i++) {
      for(size_t j = 0; j < g[i].size(); j++) {
        G[i].push_back(g[i][j]);
        rG[g[i][j]].push_back(i);
      }
    }
  }

  void SccDfsOne(int cur) {
    isthrough[cur] = true;
    for(size_t i = 0; i < G[cur].size(); i++) {
      if(!isthrough[G[cur][i]]) {
        SccDfsOne(G[cur][i]);
      }
    }
    vs.push_back(cur);
  }

  void SccDfsTwo(vector<int> &vec, int cur, int k) {
    cmp[cur] = k;
    isthrough[cur] = true;
    vec.push_back(cur);
    for(size_t i = 0; i < rG[cur].size(); i++) {
      if(!isthrough[rG[cur][i]]) {
        SccDfsTwo(vec, rG[cur][i], k);
      }
    }
  }

  // 縮約後のグループ、グループ数
  // 暫定では, 使うのはこれだけ
  pair<vector<int>, int> scc() {
    // 1回めのDFS
    for(int i = 0; i < n; i++)
      if(!isthrough[i]) SccDfsOne(i);

    fill(isthrough.begin(), isthrough.end(), false);
    reverse(vs.begin(), vs.end());
    int k = 0; vector<vector<int>> S;

    // 2回めのDFS
    for(size_t i = 0; i < vs.size(); i++) {
      if(!isthrough[vs[i]]) {
        S.push_back(vector<int>());
        SccDfsTwo(S.back(), vs[i], k++);
      }
    }

    H.resize(k);
    fill(isthrough.begin(), isthrough.end(), false);
    for(size_t i = 0; i < k; i++) {
      for(size_t j = 0; j < S[i].size(); j++) {
        int v = S[i][j];
        for(size_t x = 0; x < G[v].size(); x++) {
          int u = G[v][x];
          if(isthrough[cmp[u]] or cmp[v] == cmp[u]) continue;
          isthrough[cmp[u]] = true;
          H[cmp[v]].push_back(cmp[u]);
        }
      }
      for(size_t j=0; j<H[i].size(); j++) isthrough[H[i][j]] = false;
    }
    return make_pair(cmp, k);
  }
};

int main(){
  
  int n, m; cin >> n >> m;

  graph g(n);
  rep(i, m) {
    int a, b; cin >> a >> b;
    a--;
    b--;

    g[a].push_back(b);
  }

  StronglyConnectedComponents scc(g);
  auto hoge = scc.scc();
  auto vec = hoge.first;
  int cnt = hoge.second;


  // グループ i に属する頂点集合
  vector<vector<int>> vs(cnt);
  for(int i = 0; i < n; i++) {
    vs[vec[i]].push_back(i);
  }


  for(int i = 0; i < n; i++) {
    int val = vec[i];
    for(int j = 0; j < vs[val].size(); j++){
      cout << vs[val][j] + 1;
      if(j != vs[val].size() - 1) cout << " ";
    }
    cout << endl;
  }
  return 0;
}


### Prompt

Your challenge is to write a CPP solution 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
/* monkukui 競技プログラミング用のテンプレート  (ここから) */
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
using ll = long long int;
using lnt = long long int;
using graph = vector<vector<int>>;
using wgraph = vector<vector<pair<int, long long int>>>;
long long int INF = 1001001001001001LL;
long long int MOD = 1000000007LL;
double PI = 3.1415926535897932;
long long int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
long long int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
inline void yes(){ cout << "yes" << endl; }
inline void Yes(){ cout << "Yes" << endl; }
inline void YES(){ cout << "YES" << endl; }
inline void no(){ cout << "no" << endl; }
inline void No(){ cout << "No" << endl; }
inline void NO(){ cout << "NO" << endl; }
inline void possible(){ cout << "possible" << endl; }
inline void Possible(){ cout << "Possible" << endl; }
inline void POSSIBLE(){ cout << "POSSIBLE" << endl; }
inline void impossible(){ cout << "impossible" << endl; }
inline void Impossible(){ cout << "Impossible" << endl; }
inline void IMPOSSIBLE(){ cout << "IMPOSSIBLE" << endl; }

#define rep(i,n) for(long long int i = 0; i < (n); i++)
#define rrep(i,n) for(long long int i = 1; i <= (n); i++)
#define drep(i,n) for(long long int i = (n)-1; i >= 0; i--)
#define srep(i,s,t) for(long long int i = s; i < t; i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back

/* monkukui 競技プログラミング用のテンプレート (ここまで)*/


struct StronglyConnectedComponents {
public:
  const int n;
  vector<bool> isthrough;
  vector<int> vs, cmp;
  vector< vector<int> > G, rG, H; // グラフ、逆辺グラフ、縮約後のグラフ

  StronglyConnectedComponents(vector<vector<int>> &g) :
    n(g.size()), isthrough(n, false), cmp(n, 0), G(n), rG(n) {
    for(int i = 0; i < n; i++) {
      for(size_t j = 0; j < g[i].size(); j++) {
        G[i].push_back(g[i][j]);
        rG[g[i][j]].push_back(i);
      }
    }
  }

  void SccDfsOne(int cur) {
    isthrough[cur] = true;
    for(size_t i = 0; i < G[cur].size(); i++) {
      if(!isthrough[G[cur][i]]) {
        SccDfsOne(G[cur][i]);
      }
    }
    vs.push_back(cur);
  }

  void SccDfsTwo(vector<int> &vec, int cur, int k) {
    cmp[cur] = k;
    isthrough[cur] = true;
    vec.push_back(cur);
    for(size_t i = 0; i < rG[cur].size(); i++) {
      if(!isthrough[rG[cur][i]]) {
        SccDfsTwo(vec, rG[cur][i], k);
      }
    }
  }

  // 縮約後のグループ、グループ数
  // 暫定では, 使うのはこれだけ
  pair<vector<int>, int> scc() {
    // 1回めのDFS
    for(int i = 0; i < n; i++)
      if(!isthrough[i]) SccDfsOne(i);

    fill(isthrough.begin(), isthrough.end(), false);
    reverse(vs.begin(), vs.end());
    int k = 0; vector<vector<int>> S;

    // 2回めのDFS
    for(size_t i = 0; i < vs.size(); i++) {
      if(!isthrough[vs[i]]) {
        S.push_back(vector<int>());
        SccDfsTwo(S.back(), vs[i], k++);
      }
    }

    H.resize(k);
    fill(isthrough.begin(), isthrough.end(), false);
    for(size_t i = 0; i < k; i++) {
      for(size_t j = 0; j < S[i].size(); j++) {
        int v = S[i][j];
        for(size_t x = 0; x < G[v].size(); x++) {
          int u = G[v][x];
          if(isthrough[cmp[u]] or cmp[v] == cmp[u]) continue;
          isthrough[cmp[u]] = true;
          H[cmp[v]].push_back(cmp[u]);
        }
      }
      for(size_t j=0; j<H[i].size(); j++) isthrough[H[i][j]] = false;
    }
    return make_pair(cmp, k);
  }
};

int main(){
  
  int n, m; cin >> n >> m;

  graph g(n);
  rep(i, m) {
    int a, b; cin >> a >> b;
    a--;
    b--;

    g[a].push_back(b);
  }

  StronglyConnectedComponents scc(g);
  auto hoge = scc.scc();
  auto vec = hoge.first;
  int cnt = hoge.second;


  // グループ i に属する頂点集合
  vector<vector<int>> vs(cnt);
  for(int i = 0; i < n; i++) {
    vs[vec[i]].push_back(i);
  }


  for(int i = 0; i < n; i++) {
    int val = vec[i];
    for(int j = 0; j < vs[val].size(); j++){
      cout << vs[val][j] + 1;
      if(j != vs[val].size() - 1) cout << " ";
    }
    cout << endl;
  }
  return 0;
}


```