#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
typedef long long int ll;

struct SCC{
	vector<vector<int> > gg,rg;
	vector<int> comp,order;
	vector<bool> used;
	vector<vector<int> > ng,vs;
	int n,nn;
	SCC(){}
	SCC(int v):gg(v),rg(v),comp(v,-1),used(v,0),n(v){}
	void add_edge(int x,int y){
		gg[x].push_back(y);
		rg[y].push_back(x);
	}
	int operator[](int k){
		return comp[k];
	}
	void dfs(int v){
		used[v]=1;
		for(int i:gg[v]){
			if(!used[i])dfs(i);
		}
		order.push_back(v);
	}
	void rdfs(int v,int k){
		used[v]=1;
		comp[v]=k;
		for(int i:rg[v]){
			if(!used[i])rdfs(i,k);
		}
	}
	int build(){
		for(int i=0;i<n;i++){
			if(!used[i])dfs(i);
		}
		for(int i=0;i<n;i++){
			used[i]=0;
		}
		int k=0;
		for(int i=order.size()-1;i>=0;i--){
			if(!used[order[i]])rdfs(order[i],k++);
		}
		nn=k;
		// それぞれの強連結成分に含まれる頂点の番号
		vs.resize(k,vector<int>());
		for(int i=0;i<n;i++){
			vs[comp[i]].push_back(i);
		}
		// 強連結成分をまとめた後のグラフ
		ng.resize(k,vector<int>());
		for(int i=0;i<n;i++){
			for(int j:gg[i]){
				if(comp[i]!=comp[j]){
					ng[comp[i]].push_back(comp[j]);
				}
			}
		}
		for(int i=0;i<nn;i++){
			sort(ng[i].begin(),ng[i].end());
			ng[i].erase(unique(ng[i].begin(),ng[i].end()),ng[i].end());
		}
		return k;
	}
	int size(){
		return nn;
	}
	vector<vector<int> > graph(){
		return ng;
	}
	vector<int> vertices(int v){
		return vs[v];
	}
};

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,m; cin >> n >> m;
	SCC scc(n);
	for(int i=0;i<m;i++){
		int x,y; cin >> x >> y;
		x--; y--;
		scc.add_edge(x,y);
	}
	scc.build();
	for(int i=0;i<n;i++){
		vector<int> v;
		for(int j=0;j<n;j++){
			if(scc[i]==scc[j])v.push_back(j);
		}
		cout << v[0]+1;
		for(int k=1;k<v.size();k++){
			cout << " " << v[k]+1;
		}
		cout << endl;
	}
}


### Prompt

Create a solution in cpp for 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 <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
typedef long long int ll;

struct SCC{
	vector<vector<int> > gg,rg;
	vector<int> comp,order;
	vector<bool> used;
	vector<vector<int> > ng,vs;
	int n,nn;
	SCC(){}
	SCC(int v):gg(v),rg(v),comp(v,-1),used(v,0),n(v){}
	void add_edge(int x,int y){
		gg[x].push_back(y);
		rg[y].push_back(x);
	}
	int operator[](int k){
		return comp[k];
	}
	void dfs(int v){
		used[v]=1;
		for(int i:gg[v]){
			if(!used[i])dfs(i);
		}
		order.push_back(v);
	}
	void rdfs(int v,int k){
		used[v]=1;
		comp[v]=k;
		for(int i:rg[v]){
			if(!used[i])rdfs(i,k);
		}
	}
	int build(){
		for(int i=0;i<n;i++){
			if(!used[i])dfs(i);
		}
		for(int i=0;i<n;i++){
			used[i]=0;
		}
		int k=0;
		for(int i=order.size()-1;i>=0;i--){
			if(!used[order[i]])rdfs(order[i],k++);
		}
		nn=k;
		// それぞれの強連結成分に含まれる頂点の番号
		vs.resize(k,vector<int>());
		for(int i=0;i<n;i++){
			vs[comp[i]].push_back(i);
		}
		// 強連結成分をまとめた後のグラフ
		ng.resize(k,vector<int>());
		for(int i=0;i<n;i++){
			for(int j:gg[i]){
				if(comp[i]!=comp[j]){
					ng[comp[i]].push_back(comp[j]);
				}
			}
		}
		for(int i=0;i<nn;i++){
			sort(ng[i].begin(),ng[i].end());
			ng[i].erase(unique(ng[i].begin(),ng[i].end()),ng[i].end());
		}
		return k;
	}
	int size(){
		return nn;
	}
	vector<vector<int> > graph(){
		return ng;
	}
	vector<int> vertices(int v){
		return vs[v];
	}
};

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,m; cin >> n >> m;
	SCC scc(n);
	for(int i=0;i<m;i++){
		int x,y; cin >> x >> y;
		x--; y--;
		scc.add_edge(x,y);
	}
	scc.build();
	for(int i=0;i<n;i++){
		vector<int> v;
		for(int j=0;j<n;j++){
			if(scc[i]==scc[j])v.push_back(j);
		}
		cout << v[0]+1;
		for(int k=1;k<v.size();k++){
			cout << " " << v[k]+1;
		}
		cout << endl;
	}
}


```