stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;



const int N = (int)1e5 + 10;

const double eps = 1e-8;



template <typename T> inline T gcd(T a, T b) { a = abs(a), b = abs(b); while ( b ) { a %= b; swap(a, b); } return a; }

vector <pair <int, int> > adj[N + 7];





int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0); cout.tie(0);

	int n, m;

	cin >> n >> m;

	vector <pair <ll, ll> > arr(n);

	for ( int i = 0; i < n; ++i ) {

		cin >> arr[i].first >> arr[i].second;

	}

	sort(arr.begin(), arr.end());

	int total = 0;

	ll taka = 0;

	for ( int i = 0; i < n; ++i ) {

		int temp = m - total;

		if ( arr[i].second <= temp ) {

			total += arr[i].second;

			taka += (arr[i].second * arr[i].first);

		} else if ( arr[i].second > temp ) {

			taka += ((m - total) * arr[i].first);

			total = m;

		}

		if ( total >= m ) break;

	}

	cout << taka << endl;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.5770381660173114x):
#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

struct pp{

	int a,b;

}e[100010];

int cmp(const pp&a,const pp&b)

{

	if(a.a<b.a) return 1;

	return 0;

}

int main ()

{

	int n,m,i;

	scanf("%d%d",&n,&m);

	for(i=1;i<=n;++i) scanf("%d%d",&e[i].a,&e[i].b);

	sort(e+1,e+1+n,cmp);

	long long ans=0;

	for(i=1;i<=n;++i)

	{

		if(m>e[i].b)

		{

			m-=e[i].b;

			ans+=(long long)e[i].b*e[i].a; 

		}

		else

		{

			ans+=(long long)e[i].a*m;

			break;

		}

	} 

	printf("%lld",ans);

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

void p(int x)

{

    int i,j;

    for(i=2;i<=1000000;i++)

    {

        if(x==1){printf("\n"); return;}

        while(x%i==0)

        {

            printf(" %d",i);

            x=x/i;

        }

    }

    printf(" %d\n",x);

}

int main()

{

    int x;

    scanf("%d",&x);

    printf("%d:",x);

    p(x);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.606367842647619x):
#include<stdio.h>

#include <math.h>

int prime(int num)

{

	if(num == 1)

	{

		return 0;

	}

	int tmp = sqrt(num) + 1;

	for(int i = 2; i < tmp; i++)

	{

		if(num % i == 0)

		{

			return 0;

		}

	}

	return 1;

}

int main()

{

	int n,i,j,k;

	scanf("%d",&n);

	

	

	printf("%d:",n);

	if(prime(n))

	{

		printf(" %d\n", n);

		return 0;

	}

	for(i=2;n!=1;)

	{

		if(n%i!=0)

		{

			//if(n==2)

			i++;

			//else

			//i+=2;

		}

		else

		{

			printf(" %d",i);

			n/=i;

		}

	}

	printf("\n");

	

}
// Slower C++ solution:
#include<iostream>

#include<bits/stdc++.h>

#include<math.h>

#include<stdlib.h>

#include<stdio.h>

#include<string.h>

#include<sstream>

using namespace std;

void p(int x)

{

    int i,j;

    for(i=2;i<=1000000;i++)

    {

    if(x==1) { printf("\n"); return; }



    while(x%i==0)

      {

        printf(" %d",i);

        x=x/i;

      }

    }

    printf(" %d\n",x);

}



int main()

{

    int x;cin>>x;

    printf("%d:",x);

    p(x);



return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.642359628623952x):
#include<stdio.h>

#include <math.h>

int prime(int num)

{

	if(num == 1)

	{

		return 0;

	}

	int tmp = sqrt(num) + 1;

	for(int i = 2; i < tmp; i++)

	{

		if(num % i == 0)

		{

			return 0;

		}

	}

	return 1;

}

int main()

{

	int n,i,j,k;

	scanf("%d",&n);

	

	

	printf("%d:",n);

	if(prime(n))

	{

		printf(" %d\n", n);

		return 0;

	}

	for(i=2;n!=1;)

	{

		if(n%i!=0)

		{

			//if(n==2)

			i++;

			//else

			//i+=2;

		}

		else

		{

			printf(" %d",i);

			n/=i;

		}

	}

	printf("\n");

	

}
// Slower C++ solution:
#include<bits/stdc++.h> //Ithea Myse Valgulious

namespace chtholly{

typedef long long ll;

#define re0 register int

#define rec register char

#define rel register ll

#define gc getchar

#define pc putchar

#define p32 pc(' ')

#define pl puts("")

/*By Citrus*/

inline int read(){

  int x=0,f=1;char c=gc();

  for (;!isdigit(c);c=gc()) f^=c=='-';

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return f?x:-x;

  }

template <typename mitsuha>

inline bool read(mitsuha &x){

  x=0;int f=1;char c=gc();

  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';

  if (!~c) return 0;

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return x=f?x:-x,1;

  }

template <typename mitsuha>

inline int write(mitsuha x){

  if (!x) return 0&pc(48);

  if (x<0) x=-x,pc('-');

  int bit[20],i,p=0;

  for (;x;x/=10) bit[++p]=x%10;

  for (i=p;i;--i) pc(bit[i]+48);

  return 0;

  }

inline char fuhao(){

  char c=gc();

  for (;isspace(c);c=gc());

  return c;

  }

}using namespace chtholly;

using namespace std;

const int yuzu=2e5;

typedef int fuko[yuzu|10];

fuko u,v;int vis[2][yuzu>>6][yuzu>>6];

vector<int> lj[yuzu|10];



void dfs(int id,int p,int u,int col){

if (vis[id][p][u]) return;

vis[id][p][u]=col;

for (int i:lj[u]) dfs(id,p,i,col);

}



int main(){

int i,n=read(),m=read();

for (i=1;i<=m;++i){

  u[i]=read(),v[i]=read();

  lj[u[i]].push_back(v[i]);

  } 

for (i=1;i<=n;++i){

  vis[0][i][i]=vis[1][i][i]=1;

  int now=0;for (int j:lj[i]) dfs(0,i,j,++now);

  if (lj[i].size()) for (int j=lj[i].size()-1;~j;--j) dfs(1,i,lj[i][j],j+1);

  }

for (i=1;i<=m;++i){

  puts((vis[0][u[i]][v[i]]!=vis[1][u[i]][v[i]])^(vis[0][v[i]][u[i]]>0)?"diff":"same");

  }

}

// Faster C++ solution for the same problem (measured speedup: 6.248471781461968x):
#include<cstdio>

#include<cstring>

#include<iostream>

#include<vector>

using namespace std; 

const int maxn=1000+50;

const int maxm=200000+50;

int N,M;

int p[maxn];

int q[maxn];

int c[maxn][maxn];

bool an[maxm];

struct edge

{

	int to,id;

	edge(int to=0,int id=0):to(to),id(id){}

};

vector<edge> adj[maxn];

void dfs(int u,int root)

{

	if(c[root][u]) return;

	c[root][u]=1;

	for(unsigned int i=0;i<adj[u].size();++i)

	{

		int v=adj[u][i].to;

		dfs(v,root); 

	}

}

void dfs(int u,int c,int *p)

{

	if(p[u]!=-1) return;

	p[u]=c;

	for(unsigned int i=0;i<adj[u].size();++i)

	{

		int v=adj[u][i].to;

		dfs(v,c,p);

	}

}

void solve()

{

	for(int i=1;i<=N;++i)

	{

		dfs(i,i);

	}

	for(int u=1;u<=N;++u)

	{

		memset(p,-1,sizeof(p));

		memset(q,-1,sizeof(q));

		int l=p[u]=q[u]=adj[u].size();

		for(int i=0;i<l;++i)

		{

			int v=adj[u][i].to;

			dfs(v,i,p);

		}

		for(int i=l-1;~i;--i)

		{

			int v=adj[u][i].to;

			dfs(v,i,q);

		}

		for(int i=0;i<l;++i)

		{

			int v=adj[u][i].to;

			int d=adj[u][i].id;

			an[d]=c[v][u]^(p[v]!=i||q[v]!=i);

		}

	}

}

int main()

{

	scanf("%d%d",&N,&M);

	for(int i=1;i<=M;++i)

	{

		int a,b;

		scanf("%d%d",&a,&b);

		adj[a].push_back(edge(b,i));

	}

	solve();

	for(int i=1;i<=M;++i)

	{

		puts(an[i]?"diff":"same");

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h> //Ithea Myse Valgulious

namespace chtholly{

typedef long long ll;

#define re0 register int

#define rec register char

#define rel register ll

#define gc getchar

#define pc putchar

#define p32 pc(' ')

#define pl puts("")

/*By Citrus*/

inline int read(){

  int x=0,f=1;char c=gc();

  for (;!isdigit(c);c=gc()) f^=c=='-';

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return f?x:-x;

  }

template <typename mitsuha>

inline bool read(mitsuha &x){

  x=0;int f=1;char c=gc();

  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';

  if (!~c) return 0;

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return x=f?x:-x,1;

  }

template <typename mitsuha>

inline int write(mitsuha x){

  if (!x) return 0&pc(48);

  if (x<0) x=-x,pc('-');

  int bit[20],i,p=0;

  for (;x;x/=10) bit[++p]=x%10;

  for (i=p;i;--i) pc(bit[i]+48);

  return 0;

  }

inline char fuhao(){

  char c=gc();

  for (;isspace(c);c=gc());

  return c;

  }

}using namespace chtholly;

using namespace std;

const int yuzu=2e5;

typedef int fuko[yuzu|10];

fuko u,v;int vis[2][yuzu>>6][yuzu>>6];

vector<int> lj[yuzu|10];



void dfs(int id,int p,int u,int col){

if (vis[id][p][u]) return;

vis[id][p][u]=col;

for (int i:lj[u]) dfs(id,p,i,col);

}



int main(){

int i,n=read(),m=read();

for (i=1;i<=m;++i){

  u[i]=read(),v[i]=read();

  lj[u[i]].push_back(v[i]);

  } 

for (i=1;i<=n;++i){

  vis[0][i][i]=vis[1][i][i]=1;

  int now=0;for (int j:lj[i]) dfs(0,i,j,++now);

  if (lj[i].size()) for (int j=lj[i].size()-1;~j;--j) dfs(1,i,lj[i][j],j+1);

  }

for (i=1;i<=m;++i){

  puts((vis[0][u[i]][v[i]]!=vis[1][u[i]][v[i]])^(vis[0][v[i]][u[i]]>0)?"diff":"same");

  }

}

// Faster C++ solution for the same problem (measured speedup: 6.709371017652504x):
#include<cstdio>

#include<cstring>

#include<vector>

using namespace std;

int n,m,u[210000],v[210000],tmp[1100][2];

bool ans1[1100][1100],ans2[1100][1100];

vector<int> vec[1100];

void dfs(int u,int rt){

    ans1[rt][u]=true;

    for(int i=0;i<vec[u].size();i++)

        if (!ans1[rt][vec[u][i]]) dfs(vec[u][i],rt);

}

void dfs2(int u,int num,int f){

    tmp[u][f]=num;

    for(int i=0;i<vec[u].size();i++)

        if (!tmp[vec[u][i]][f]) dfs2(vec[u][i],num,f);

}

int main(){

    scanf("%d%d",&n,&m);

    for (int i=1;i<=m;i++){

        scanf("%d%d",&u[i],&v[i]);

        vec[u[i]].push_back(v[i]);

    }

    for (int i=1;i<=n;i++) dfs(i,i);

    for (int i=1;i<=n;i++){

        memset(tmp,0,sizeof(tmp));

        tmp[i][0]=-1; tmp[i][1]=-1;

        for (int j=0;j<vec[i].size();j++)

            if (!tmp[vec[i][j]][0]) dfs2(vec[i][j],j+1,0);

        for (int j=vec[i].size()-1;j>=0;j--)

            if (!tmp[vec[i][j]][1]) dfs2(vec[i][j],j+1,1);

        for (int j=0;j<vec[i].size();j++)

            if (tmp[vec[i][j]][0]!=j+1||tmp[vec[i][j]][1]!=j+1) ans2[i][vec[i][j]]=true;

    }

    for (int i=1;i<=m;i++)

        if (ans1[v[i]][u[i]]==ans2[u[i]][v[i]]) puts("same");

        else puts("diff");

    

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h> //Ithea Myse Valgulious

namespace chtholly{

typedef long long ll;

#define re0 register int

#define rec register char

#define rel register ll

#define gc getchar

#define pc putchar

#define p32 pc(' ')

#define pl puts("")

/*By Citrus*/

inline int read(){

  int x=0,f=1;char c=gc();

  for (;!isdigit(c);c=gc()) f^=c=='-';

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return f?x:-x;

  }

template <typename mitsuha>

inline bool read(mitsuha &x){

  x=0;int f=1;char c=gc();

  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';

  if (!~c) return 0;

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return x=f?x:-x,1;

  }

template <typename mitsuha>

inline int write(mitsuha x){

  if (!x) return 0&pc(48);

  if (x<0) x=-x,pc('-');

  int bit[20],i,p=0;

  for (;x;x/=10) bit[++p]=x%10;

  for (i=p;i;--i) pc(bit[i]+48);

  return 0;

  }

inline char fuhao(){

  char c=gc();

  for (;isspace(c);c=gc());

  return c;

  }

}using namespace chtholly;

using namespace std;

const int yuzu=2e5;

typedef int fuko[yuzu|10];

fuko u,v;int vis[2][yuzu>>6][yuzu>>6];

vector<int> lj[yuzu|10];



void dfs(int id,int p,int u,int col){

if (vis[id][p][u]) return;

vis[id][p][u]=col;

for (int i:lj[u]) dfs(id,p,i,col);

}



int main(){

int i,n=read(),m=read();

for (i=1;i<=m;++i){

  u[i]=read(),v[i]=read();

  lj[u[i]].push_back(v[i]);

  } 

for (i=1;i<=n;++i){

  vis[0][i][i]=vis[1][i][i]=1;

  int now=0;for (int j:lj[i]) dfs(0,i,j,++now);

  if (lj[i].size()) for (int j=lj[i].size()-1;~j;--j) dfs(1,i,lj[i][j],j+1);

  }

for (i=1;i<=m;++i){

  puts((vis[0][u[i]][v[i]]!=vis[1][u[i]][v[i]])^(vis[0][v[i]][u[i]]>0)?"diff":"same");

  }

}

// Faster C++ solution for the same problem (measured speedup: 6.338359394065953x):
#include <bits/stdc++.h>

using namespace std;

#define N 1010

#define M 200010

vector <int> G[N];

int to[M],tag[N],q[2*N];

bool ans1[M],ans2[M];

int read(){

	int x=0,f=1;

	char ch=getchar();

	while (ch<'0' || ch>'9'){

		if (ch=='-') f=-1;

		ch=getchar();

	}

	while (ch>='0' && ch<='9'){

		x=x*10+ch-'0';ch=getchar();

	}

	return x*f;

}

signed main(){

	int n=read(),m=read();

	for (int i=1;i<=m;++i){

		int x=read();to[i]=read();

		G[x].push_back(i);

	}

	for (int i=1;i<=n;++i){

		for (int j=1;j<=n;++j) tag[j]=0;

		int t=1,w=0;

		for (auto &x:G[i]){

			q[++w]=to[x];tag[to[x]]=x;

		}

		while (t<=w){

			int x=q[t++],y=tag[x];

			for (auto &p:G[x]){

				int tmp=to[p];

				if (tmp!=i){

					if (tag[tmp]!=-1){

						if (tag[tmp]==0){

							q[++w]=tmp;tag[tmp]=y;

						}else if (tag[tmp]!=y){

							q[++w]=tmp;tag[tmp]=-1;

						}

					}

				}else ans1[p]=1;

			}

		}

		for (auto &x:G[i]){

			if (tag[to[x]]==-1) ans2[x]=1;

		}

	}

	for (int i=1;i<=m;++i) puts(ans1[i]^ans2[i]?"diff":"same");

	return 0; 

}
// Slower C++ solution:
#include<bits/stdc++.h> //Ithea Myse Valgulious

namespace chtholly{

typedef long long ll;

#define re0 register int

#define rec register char

#define rel register ll

#define gc getchar

#define pc putchar

#define p32 pc(' ')

#define pl puts("")

/*By Citrus*/

inline int read(){

  int x=0,f=1;char c=gc();

  for (;!isdigit(c);c=gc()) f^=c=='-';

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return f?x:-x;

  }

template <typename mitsuha>

inline bool read(mitsuha &x){

  x=0;int f=1;char c=gc();

  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';

  if (!~c) return 0;

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return x=f?x:-x,1;

  }

template <typename mitsuha>

inline int write(mitsuha x){

  if (!x) return 0&pc(48);

  if (x<0) x=-x,pc('-');

  int bit[20],i,p=0;

  for (;x;x/=10) bit[++p]=x%10;

  for (i=p;i;--i) pc(bit[i]+48);

  return 0;

  }

inline char fuhao(){

  char c=gc();

  for (;isspace(c);c=gc());

  return c;

  }

}using namespace chtholly;

using namespace std;

const int yuzu=2e5;

typedef int fuko[yuzu|10];

fuko u,v;int vis[2][yuzu>>6][yuzu>>6];

vector<int> lj[yuzu|10];



void dfs(int id,int p,int u,int col){

if (vis[id][p][u]) return;

vis[id][p][u]=col;

for (int i:lj[u]) dfs(id,p,i,col);

}



int main(){

int i,n=read(),m=read();

for (i=1;i<=m;++i){

  u[i]=read(),v[i]=read();

  lj[u[i]].push_back(v[i]);

  } 

for (i=1;i<=n;++i){

  vis[0][i][i]=vis[1][i][i]=1;

  int now=0;for (int j:lj[i]) dfs(0,i,j,++now);

  if (lj[i].size()) for (int j=lj[i].size()-1;~j;--j) dfs(1,i,lj[i][j],j+1);

  }

for (i=1;i<=m;++i){

  puts((vis[0][u[i]][v[i]]!=vis[1][u[i]][v[i]])^(vis[0][v[i]][u[i]]>0)?"diff":"same");

  }

}

// Faster C++ solution for the same problem (measured speedup: 6.307515288484757x):
#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<vector>

#include<bitset>

using namespace std;

const int MAXN=1005,MAXM=200005;

int n,m;

int ex[MAXM],ey[MAXM];

vector<int> ver[MAXN];

bool ok[MAXN][MAXN];

void dfs(int u,bool tag[]) {

	tag[u]=1;

	for(int v:ver[u])

		if(!tag[v]) dfs(v,tag);

}

int a[MAXN][MAXN],b[MAXN][MAXN];

void mak_tag(int u,int tag[],int id) {

	tag[u]=id;

	for(int v:ver[u]) if(!tag[v])

		mak_tag(v,tag,id);

}



int main() {

	scanf("%d%d",&n,&m);

	for(int i=1,x,y;i<=m;i++) {

		scanf("%d%d",&x,&y);

		ver[x].push_back(y);

		ex[i]=x,ey[i]=y;

	}

	

	for(int i=1;i<=n;i++)

		dfs(i,ok[i]);

	for(int i=1;i<=n;i++) {

		a[i][i]=-1;

		for(int j=0;j<(int)ver[i].size();j++)

			if(!a[i][ver[i][j]]) mak_tag(ver[i][j],a[i],j+1);

	}

	for(int i=1;i<=n;i++) {

		b[i][i]=-1;

		for(int j=ver[i].size()-1;~j;j--)

			if(!b[i][ver[i][j]]) mak_tag(ver[i][j],b[i],j+1);

	}



	for(int i=1;i<=m;i++) {

		int x=ex[i],y=ey[i];

		puts((ok[y][x])^(a[x][y]!=b[x][y])?"diff":"same");

	}

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h> //Ithea Myse Valgulious

namespace chtholly{

typedef long long ll;

#define re0 register int

#define rec register char

#define rel register ll

#define gc getchar

#define pc putchar

#define p32 pc(' ')

#define pl puts("")

/*By Citrus*/

inline int read(){

  int x=0,f=1;char c=gc();

  for (;!isdigit(c);c=gc()) f^=c=='-';

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return f?x:-x;

  }

template <typename mitsuha>

inline bool read(mitsuha &x){

  x=0;int f=1;char c=gc();

  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';

  if (!~c) return 0;

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return x=f?x:-x,1;

  }

template <typename mitsuha>

inline int write(mitsuha x){

  if (!x) return 0&pc(48);

  if (x<0) x=-x,pc('-');

  int bit[20],i,p=0;

  for (;x;x/=10) bit[++p]=x%10;

  for (i=p;i;--i) pc(bit[i]+48);

  return 0;

  }

inline char fuhao(){

  char c=gc();

  for (;isspace(c);c=gc());

  return c;

  }

}using namespace chtholly;

using namespace std;

const int yuzu=2e5;

typedef int fuko[yuzu|10];

fuko u,v;int vis[2][yuzu>>6][yuzu>>6];

vector<int> lj[yuzu|10];



void dfs(int id,int p,int u,int col){

if (vis[id][p][u]) return;

vis[id][p][u]=col;

for (int i:lj[u]) dfs(id,p,i,col);

}



int main(){

int i,n=read(),m=read();

for (i=1;i<=m;++i){

  u[i]=read(),v[i]=read();

  lj[u[i]].push_back(v[i]);

  } 

for (i=1;i<=n;++i){

  vis[0][i][i]=vis[1][i][i]=1;

  int now=0;for (int j:lj[i]) dfs(0,i,j,++now);

  if (lj[i].size()) for (int j=lj[i].size()-1;~j;--j) dfs(1,i,lj[i][j],j+1);

  }

for (i=1;i<=m;++i){

  puts((vis[0][u[i]][v[i]]!=vis[1][u[i]][v[i]])^(vis[0][v[i]][u[i]]>0)?"diff":"same");

  }

}

// Faster C++ solution for the same problem (measured speedup: 6.301850915578729x):
#include <bits/stdc++.h>

using namespace std;

const int N = 1005, M = 2e5 + 10;

int n, m, u[M], v[M], ok[N][N], pos[N][N], vis[N][N], ok2[N][N];

vector<int> g[N];

void dfs(int h, int u) {

    ok[u][h] = 1;

    for(auto v : g[u]) if(!ok[v][h]) dfs(h, v);

}

void dfs1(int h, int u, int fr) {

    pos[h][u] = fr;

    for(auto v : g[u])

        if(!pos[h][v]) dfs1(h, v, u);

}

void dfs2(int h, int u) {

    vis[h][u] = 1;

    for(int i = g[u].size() - 1; i >= 0; --i) {

        int v = g[u][i];

        if(!vis[h][v]) {

            if(pos[h][v] != u || u != h) ok2[h][v] = 1;

            dfs2(h, v);

        }

    }

}

int main() {

    scanf("%d %d", &n, &m);

    for(int i = 1; i <= m; ++i) 

        scanf("%d %d", &u[i], &v[i]), g[u[i]].push_back(v[i]);

    for(int i = 1; i <= n; ++i) dfs(i, i);

    for(int i = 1; i <= n; ++i) dfs1(i, i, i);

    for(int i = 1; i <= n; ++i) dfs2(i, i);

    for(int i = 1; i <= m; ++i) {

        if(ok[u[i]][v[i]] ^ ok2[u[i]][v[i]]) printf("diff\n");

        else printf("same\n");

    }

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h> //Ithea Myse Valgulious

namespace chtholly{

typedef long long ll;

#define re0 register int

#define rec register char

#define rel register ll

#define gc getchar

#define pc putchar

#define p32 pc(' ')

#define pl puts("")

/*By Citrus*/

inline int read(){

  int x=0,f=1;char c=gc();

  for (;!isdigit(c);c=gc()) f^=c=='-';

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return f?x:-x;

  }

template <typename mitsuha>

inline bool read(mitsuha &x){

  x=0;int f=1;char c=gc();

  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';

  if (!~c) return 0;

  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');

  return x=f?x:-x,1;

  }

template <typename mitsuha>

inline int write(mitsuha x){

  if (!x) return 0&pc(48);

  if (x<0) x=-x,pc('-');

  int bit[20],i,p=0;

  for (;x;x/=10) bit[++p]=x%10;

  for (i=p;i;--i) pc(bit[i]+48);

  return 0;

  }

inline char fuhao(){

  char c=gc();

  for (;isspace(c);c=gc());

  return c;

  }

}using namespace chtholly;

using namespace std;

const int yuzu=2e5;

typedef int fuko[yuzu|10];

fuko u,v;int vis[2][yuzu>>6][yuzu>>6];

vector<int> lj[yuzu|10];



void dfs(int id,int p,int u,int col){

if (vis[id][p][u]) return;

vis[id][p][u]=col;

for (int i:lj[u]) dfs(id,p,i,col);

}



int main(){

int i,n=read(),m=read();

for (i=1;i<=m;++i){

  u[i]=read(),v[i]=read();

  lj[u[i]].push_back(v[i]);

  } 

for (i=1;i<=n;++i){

  vis[0][i][i]=vis[1][i][i]=1;

  int now=0;for (int j:lj[i]) dfs(0,i,j,++now);

  if (lj[i].size()) for (int j=lj[i].size()-1;~j;--j) dfs(1,i,lj[i][j],j+1);

  }

for (i=1;i<=m;++i){

  puts((vis[0][u[i]][v[i]]!=vis[1][u[i]][v[i]])^(vis[0][v[i]][u[i]]>0)?"diff":"same");

  }

}

// Faster C++ solution for the same problem (measured speedup: 6.285430904075969x):
#include<bits/stdc++.h>

using namespace std;

const int maxn=1e3+7,maxm=2e5+7;

int c[2][maxn][maxn];

vector<int> G[maxn];

int a[maxm],b[maxm];

void dfs(int x,int st,int ptr,bool typ){

	if(!c[typ][st][x]) c[typ][st][x]=ptr;else return ;//cout<<st<<' '<<x<<endl;

	for(int y:G[x]) if(!c[typ][st][y]) dfs(y,st,ptr,typ);

}

int main(){

	int n,m;cin>>n>>m;

	for(int i=1;i<=m;++i) scanf("%d%d",&a[i],&b[i]),G[a[i]].push_back(b[i]);

	for(int x=1;x<=n;++x) {

		c[0][x][x]=c[1][x][x]=1;

		for(auto y:G[x]) dfs(y,x,y,0);

		reverse(G[x].begin(),G[x].end());

		for(auto y:G[x]) dfs(y,x,y,1);

	}

	for(int i=1;i<=m;++i){

		bool flag=(c[0][b[i]][a[i]]>0);//cout<<flag<<endl;

		if(c[0][a[i]][b[i]]!=c[1][a[i]][b[i]]) flag^=1;//cout<<c[0][3][4]<<' '<<c[1][3][4]<<' '<<a[i]<<' '<<b[i]<<endl;

		if(flag) puts("diff");else puts("same");

	}

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



namespace SCC {

	const int N = 110000;

	vector<int> con[N], rcon[N];

	int n, vis[N], visT;

	int id[N], idn;

	void init(int nn = 0) {

		n = nn, visT = idn = 0;

		for (int i = 1; i <= n; i++) con[i].clear(), rcon[i].clear();

	}

	void add_edge(int u, int v) {

		con[u].push_back(v);

		rcon[v].push_back(u);

	}

	void dfs(int u) {

		vis[u] = 1;

		for (int v : con[u]) if (!vis[v]) dfs(v);

		id[idn++] = u;

	}

	void rdfs(int u) {

		vis[u] = visT;

		for (int v : rcon[u]) if (!vis[v]) rdfs(v);

	}

	void SCC() {

		for (int i = 1; i <= n; i++) vis[i] = 0;

		for (int i = 1; i <= n; i++) if (!vis[i]) dfs(i);

		for (int i = 1; i <= n; i++) vis[i] = 0;

		for (int i = idn - 1; i >= 0; i--) if (!vis[id[i]]) visT++, rdfs(id[i]);

	}

};



const int N = 1100;

const int M = 220000;



vector<int> con[N];



struct Edge {

	int u, v;

	Edge(int u = 0, int v = 0) : u(u), v(v) {}

} E[M];



int adj[N][N];

int vis[N], visT;

int son[2][N][N];



inline bool Find(int u, int tar) {

	if (adj[u][tar] > 1) return true;

	return son[0][u][tar] != tar || son[1][u][tar] != tar;

}



void dfs(int u, int id, int rt, int __rt) {

	vis[u] = visT;

	son[id][__rt][u] = rt;

	for (int v : con[u]) if (vis[v] != visT) dfs(v, id, rt, __rt);

}



void init(int n) {

	for (int i = 1; i <= n; i++) {

		visT++;

		vis[i] = visT;

		for (int v : con[i]) if (vis[v] != visT) dfs(v, 0, v, i);

		reverse(con[i].begin(), con[i].end());

		visT++;

		vis[i] = visT;

		for (int v : con[i]) if (vis[v] != visT) dfs(v, 1, v, i);

	}

}



int main() {

	

	ios::sync_with_stdio(0);

	cin.tie(0), cout.tie(0);

	

	int n, m; cin >> n >> m;

	SCC::init(n + 10);

	for (int i = 0; i < m; i++) {

		int u, v; cin >> u >> v;

		E[i] = Edge(u, v);

		con[u].push_back(v);

		adj[u][v]++;

		SCC::add_edge(u, v);

	}

	SCC::SCC();

	

	init(n);

	

	for (int i = 0; i < m; i++) {

		auto a = SCC::vis[E[i].u], b = SCC::vis[E[i].v];

		if (a == b) {

			if (Find(E[i].u, E[i].v)) cout << "same\n";

			else cout << "diff\n";

		} else {

			if (Find(E[i].u, E[i].v)) cout << "diff\n";

			else cout << "same\n";

		}

	}

	

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 8.869203134684147x):
#include<bits/stdc++.h>

using namespace std;

const int maxn=1e3+7,maxm=2e5+7;

int c[2][maxn][maxn];

vector<int> G[maxn];

int a[maxm],b[maxm];

void dfs(int x,int st,int ptr,bool typ){

	if(!c[typ][st][x]) c[typ][st][x]=ptr;else return ;//cout<<st<<' '<<x<<endl;

	for(int y:G[x]) if(!c[typ][st][y]) dfs(y,st,ptr,typ);

}

int main(){

	int n,m;cin>>n>>m;

	for(int i=1;i<=m;++i) scanf("%d%d",&a[i],&b[i]),G[a[i]].push_back(b[i]);

	for(int x=1;x<=n;++x) {

		c[0][x][x]=c[1][x][x]=1;

		for(auto y:G[x]) dfs(y,x,y,0);

		reverse(G[x].begin(),G[x].end());

		for(auto y:G[x]) dfs(y,x,y,1);

	}

	for(int i=1;i<=m;++i){

		bool flag=(c[0][b[i]][a[i]]>0);//cout<<flag<<endl;

		if(c[0][a[i]][b[i]]!=c[1][a[i]][b[i]]) flag^=1;//cout<<c[0][3][4]<<' '<<c[1][3][4]<<' '<<a[i]<<' '<<b[i]<<endl;

		if(flag) puts("diff");else puts("same");

	}

	return 0;

}