#include <bits/stdc++.h>
using namespace std;

struct Strongly_Connected_Component {
  int vsize;
  vector<vector<int>> G, reverseG;
  vector<int> vs, cmp;
  vector<bool> used;
  Strongly_Connected_Component(int newv = 1) {
    vsize = newv;
    G.resize(vsize);
    reverseG.resize(vsize);
    used.resize(vsize, 0);
    cmp.resize(vsize);
  }

  bool add(int from, int to) {
    G[from].push_back(to);
    reverseG[to].push_back(from);
    return 1;
  }
  void dfs(int v) {
    used[v] = true;
    int gvsize = G[v].size();
    for(int i = 0; i < gvsize; ++i)
      if(!used[G[v][i]]) dfs(G[v][i]);
    vs.push_back(v);
  }
  void rdfs(int v, int k) {
    used[v] = true;
    cmp[v] = k;
    int rgvsize = reverseG[v].size();
    for(int i = 0; i < rgvsize; ++i)
      if(!used[reverseG[v][i]]) rdfs(reverseG[v][i], k);
  }
  int solve() {
    used.assign(vsize, 0);
    vs.clear();
    for(int v = 0; v < vsize; ++v)
      if(!used[v]) dfs(v);
    used.assign(vsize, 0);
    int k = 0;
    for(int i = (int)vs.size() - 1; i >= 0; --i)
      if(!used[vs[i]]) rdfs(vs[i], k++);
    return k;
  }
  bool issame(int l, int r) { return cmp[l] == cmp[r]; }
};

int n, m;
Strongly_Connected_Component scc;

int main() {
  cin >> n >> m;
  scc = Strongly_Connected_Component(n);
  for(int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    scc.add(--a, --b);
  }
  scc.solve();
  for(int i = 0; i < n; ++i) {
    vector<int> v;
    for(int j = 0; j < n; ++j)
      if(scc.issame(i, j)) v.push_back(j);
    for(int j = 0; j < v.size(); ++j) {
      if(j != 0) cout << " ";
      cout << v[j] + 1;
    }
    cout << endl;
  }
  return 0;
}

### Prompt

Please provide a CPP coded solution 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>
using namespace std;

struct Strongly_Connected_Component {
  int vsize;
  vector<vector<int>> G, reverseG;
  vector<int> vs, cmp;
  vector<bool> used;
  Strongly_Connected_Component(int newv = 1) {
    vsize = newv;
    G.resize(vsize);
    reverseG.resize(vsize);
    used.resize(vsize, 0);
    cmp.resize(vsize);
  }

  bool add(int from, int to) {
    G[from].push_back(to);
    reverseG[to].push_back(from);
    return 1;
  }
  void dfs(int v) {
    used[v] = true;
    int gvsize = G[v].size();
    for(int i = 0; i < gvsize; ++i)
      if(!used[G[v][i]]) dfs(G[v][i]);
    vs.push_back(v);
  }
  void rdfs(int v, int k) {
    used[v] = true;
    cmp[v] = k;
    int rgvsize = reverseG[v].size();
    for(int i = 0; i < rgvsize; ++i)
      if(!used[reverseG[v][i]]) rdfs(reverseG[v][i], k);
  }
  int solve() {
    used.assign(vsize, 0);
    vs.clear();
    for(int v = 0; v < vsize; ++v)
      if(!used[v]) dfs(v);
    used.assign(vsize, 0);
    int k = 0;
    for(int i = (int)vs.size() - 1; i >= 0; --i)
      if(!used[vs[i]]) rdfs(vs[i], k++);
    return k;
  }
  bool issame(int l, int r) { return cmp[l] == cmp[r]; }
};

int n, m;
Strongly_Connected_Component scc;

int main() {
  cin >> n >> m;
  scc = Strongly_Connected_Component(n);
  for(int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    scc.add(--a, --b);
  }
  scc.solve();
  for(int i = 0; i < n; ++i) {
    vector<int> v;
    for(int j = 0; j < n; ++j)
      if(scc.issame(i, j)) v.push_back(j);
    for(int j = 0; j < v.size(); ++j) {
      if(j != 0) cout << " ";
      cout << v[j] + 1;
    }
    cout << endl;
  }
  return 0;
}

```