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
#include<bits/stdc++.h>
using namespace std;
using Int = signed;
//INSERT ABOVE HERE
Int dp[2][1010][1010];
Int pv[1010][1010];
signed main(){
  Int n,m;
  cin>>n>>m;
  vector<Int> a(m),b(m);
  for(Int i=0;i<m;i++) cin>>a[i]>>b[i],a[i]--,b[i]--;

  vector<vector<Int> > G(n);
  for(Int i=0;i<m;i++) G[a[i]].emplace_back(b[i]);

  memset(dp,0,sizeof(dp));
  memset(pv,-1,sizeof(pv));
  
  using T = tuple<Int, Int, Int>;
  queue<T> q;
  for(Int i=0;i<m;i++){
    pv[a[i]][b[i]]=i;
    dp[0][a[i]][b[i]]=1;
    q.emplace(0,a[i],b[i]);
  }
  while(!q.empty()){
    Int t,x,y;
    tie(t,x,y)=q.front();q.pop();
    //cout<<t<<":"<<x<<":"<<y<<"::"<<pv[x][y]<<endl;
    for(Int z:G[y]){
      if(x==z) continue;
      Int nt=t||(~pv[x][z]&&pv[x][y]!=pv[x][z]);
      if(dp[nt][x][z]) continue;
      if(pv[x][z]<0) pv[x][z]=pv[x][y];
      dp[nt][x][z]=1;
      q.emplace(nt,x,z);
    }    
  }

  for(Int i=0;i<m;i++){
    Int s=dp[1][a[i]][b[i]];
    Int t=dp[0][b[i]][a[i]]|dp[1][b[i]][a[i]];
    //cout<<s<<" "<<t<<endl;
    cout<<(s^t?"diff":"same")<<endl;
  }
  
  return 0;
}
