#include <iostream>
#include <vector>

using namespace std;
struct edge{int num,to;};
vector<int> G[100010],rG[100010],vs;
bool used[100010];
int comp[100010],n,m,ans = 0;
void add_edge(int from, int to){
	G[from].push_back(to);
	rG[to].push_back(from);
}

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

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

int scc(){
	int i,k = 0;
	for(i=0;i<n;i++) used[i] = false;
	for(i=0;i<n;i++){
		if(!used[i]) dfs(i);
	}
	for(i=0;i<n;i++) used[i] = false;
	for(i=vs.size()-1;i>=0;i--){
		if(!used[vs[i]]){
			rdfs(vs[i],k); k++;
		}
	}
	return k;
}

int main(){
	int i,j;
	cin >> n >> m;
	for(i=0;i<m;i++){
		int a,b; cin >> a >> b; a--; b--;
		add_edge(a,b);
	}
	int x = scc();
	for(i=0;i<n;i++){
		x = comp[i];
		bool flag = false;
		for(j=0;j<n;j++){
			if(comp[j]==x){
				if(flag) cout << " ";
				flag = true;
				cout << j + 1;
			}
		}
		cout << endl;
	}
}

### Prompt

Construct a cpp code solution to the problem outlined:

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>

using namespace std;
struct edge{int num,to;};
vector<int> G[100010],rG[100010],vs;
bool used[100010];
int comp[100010],n,m,ans = 0;
void add_edge(int from, int to){
	G[from].push_back(to);
	rG[to].push_back(from);
}

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

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

int scc(){
	int i,k = 0;
	for(i=0;i<n;i++) used[i] = false;
	for(i=0;i<n;i++){
		if(!used[i]) dfs(i);
	}
	for(i=0;i<n;i++) used[i] = false;
	for(i=vs.size()-1;i>=0;i--){
		if(!used[vs[i]]){
			rdfs(vs[i],k); k++;
		}
	}
	return k;
}

int main(){
	int i,j;
	cin >> n >> m;
	for(i=0;i<m;i++){
		int a,b; cin >> a >> b; a--; b--;
		add_edge(a,b);
	}
	int x = scc();
	for(i=0;i<n;i++){
		x = comp[i];
		bool flag = false;
		for(j=0;j<n;j++){
			if(comp[j]==x){
				if(flag) cout << " ";
				flag = true;
				cout << j + 1;
			}
		}
		cout << endl;
	}
}

```