#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define per(i,x,y) for (int i=(x); i>=(y); i--)
#define ll long long
#define N 1005
#define M 200005
using namespace std;
ll read(){
	char ch=getchar(); ll x=0; int op=1;
	for (; !isdigit(ch); ch=getchar()) if (ch=='-') op=-1;
	for (; isdigit(ch); ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
	return x*op;
}
int n,m,a[N][N],x[M],y[M],z[M],vis[N],p[N][N],q[N][N];
vector<int> e[N];
void dfs(int st,int u){
	vis[u]=1; a[st][u]=1;
	rep (i,0,(int)e[u].size()-1){
		int v=e[u][i]; if (!vis[v]) dfs(st,v);
	}
}
void dfs1(int st,int u,int id){
	vis[u]=1; p[st][u]=id;
	rep (i,0,(int)e[u].size()-1){
		int v=e[u][i]; if (!vis[v]) dfs1(st,v,id);
	}
}
void dfs2(int st,int u,int id){
	vis[u]=1; q[st][u]=id;
	rep (i,0,(int)e[u].size()-1){
		int v=e[u][i]; if (!vis[v]) dfs2(st,v,id);
	}
}
int main(){
	n=read(); m=read();
	rep (i,1,m){
		x[i]=read(),y[i]=read(); z[i]=(int)e[x[i]].size();
		e[x[i]].push_back(y[i]);
	}
	rep (i,1,n){
		memset(vis,0,sizeof(vis));
		dfs(i,i);
	}
	rep (i,1,n){
		memset(vis,0,sizeof(vis)); vis[i]=1;
		rep (j,0,(int)e[i].size()-1) if (!vis[e[i][j]]) dfs1(i,e[i][j],j);
		memset(vis,0,sizeof(vis)); vis[i]=1;
		per (j,(int)e[i].size()-1,0) if (!vis[e[i][j]]){
			dfs2(i,e[i][j],j);
		}
	}
	//printf("%d\n",a[3][1]);
	//printf("%d %d\n",p[1][3],q[1][3]);
	//printf("%d\n",a[4][3]);
	//printf("%d %d\n",p[3][4],q[3][4]);
	rep (i,1,m){
		bool f1=a[y[i]][x[i]];
		bool f2=p[x[i]][y[i]]!=z[i] || q[x[i]][y[i]]!=z[i];
		if (f1==f2) puts("same"); else puts("diff");
	}
	return 0;
}
### Prompt

In cpp, your task is to solve the following problem:

You are given a directed graph with N vertices and M edges. The vertices are numbered 1, 2, ..., N, and the edges are numbered 1, 2, ..., M. Edge i points from Vertex a_i to Vertex b_i.

For each edge, determine whether the reversion of that edge would change the number of the strongly connected components in the graph.

Here, the reversion of Edge i means deleting Edge i and then adding a new edge that points from Vertex b_i to Vertex a_i.

Constraints

* 2 \leq N \leq 1000
* 1 \leq M \leq 200,000
* 1 \leq a_i, b_i \leq N
* a_i \neq b_i
* If i \neq j, then a_i \neq a_j or b_i \neq b_j.

Input

Input is given from Standard Input in the following format:


N M
a_1 b_1
a_2 b_2
:
a_M b_M


Output

Print M lines. In the i-th line, if the reversion of Edge i would change the number of the strongly connected components in the graph, print `diff`; if it would not, print `same`.

Examples

Input

3 3
1 2
1 3
2 3


Output

same
diff
same


Input

2 2
1 2
2 1


Output

diff
diff


Input

5 9
3 2
3 1
4 1
4 2
3 5
5 3
3 4
1 2
2 5


Output

same
same
same
same
same
diff
diff
diff
diff

### Response

```cpp
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define per(i,x,y) for (int i=(x); i>=(y); i--)
#define ll long long
#define N 1005
#define M 200005
using namespace std;
ll read(){
	char ch=getchar(); ll x=0; int op=1;
	for (; !isdigit(ch); ch=getchar()) if (ch=='-') op=-1;
	for (; isdigit(ch); ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
	return x*op;
}
int n,m,a[N][N],x[M],y[M],z[M],vis[N],p[N][N],q[N][N];
vector<int> e[N];
void dfs(int st,int u){
	vis[u]=1; a[st][u]=1;
	rep (i,0,(int)e[u].size()-1){
		int v=e[u][i]; if (!vis[v]) dfs(st,v);
	}
}
void dfs1(int st,int u,int id){
	vis[u]=1; p[st][u]=id;
	rep (i,0,(int)e[u].size()-1){
		int v=e[u][i]; if (!vis[v]) dfs1(st,v,id);
	}
}
void dfs2(int st,int u,int id){
	vis[u]=1; q[st][u]=id;
	rep (i,0,(int)e[u].size()-1){
		int v=e[u][i]; if (!vis[v]) dfs2(st,v,id);
	}
}
int main(){
	n=read(); m=read();
	rep (i,1,m){
		x[i]=read(),y[i]=read(); z[i]=(int)e[x[i]].size();
		e[x[i]].push_back(y[i]);
	}
	rep (i,1,n){
		memset(vis,0,sizeof(vis));
		dfs(i,i);
	}
	rep (i,1,n){
		memset(vis,0,sizeof(vis)); vis[i]=1;
		rep (j,0,(int)e[i].size()-1) if (!vis[e[i][j]]) dfs1(i,e[i][j],j);
		memset(vis,0,sizeof(vis)); vis[i]=1;
		per (j,(int)e[i].size()-1,0) if (!vis[e[i][j]]){
			dfs2(i,e[i][j],j);
		}
	}
	//printf("%d\n",a[3][1]);
	//printf("%d %d\n",p[1][3],q[1][3]);
	//printf("%d\n",a[4][3]);
	//printf("%d %d\n",p[3][4],q[3][4]);
	rep (i,1,m){
		bool f1=a[y[i]][x[i]];
		bool f2=p[x[i]][y[i]]!=z[i] || q[x[i]][y[i]]!=z[i];
		if (f1==f2) puts("same"); else puts("diff");
	}
	return 0;
}
```