#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<vector>

#include<algorithm>

using namespace std;

const int maxn=30,maxm=300,K=10,A=7,B=3,C=4,P=10007,D=35;

int a[maxm][2],co[maxn],f[maxn],tf[maxn],n,m,cot[maxn];

void graph_hash()

{

 int q,w,e;

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

 	{

 	 for( q=1;q<=n;q++)f[q]=1;

 	 for(int z=0;z<K;z++)

 	 	{

 	 	 memcpy(tf,f,sizeof(f));

		 for(q=1;q<=n;q++)f[q]*=A;

		 for(q=0;q<m;q++)

		 	{

		 	 f[a[q][0]]+=tf[a[q][1]]*B;

		 	 f[a[q][1]]+=tf[a[q][0]]*C;

			}

		 f[i]+=D;

		 for(q=1;q<=n;q++)f[q]%=P;

		}

	 co[i]=f[i];

	}

sort(co+1,co+1+n);

}

int main()

{

 int kt;scanf("%d",&kt);

 for(int ii=0;ii<kt;ii++)

 	{

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

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

 	 	{

		  scanf("%d%d",&a[i][0],&a[i][1]);

		  a[i+m][0]=a[i][1];

		  a[i+m][1]=a[i][0];

		}

	 m=m*2;

	 graph_hash();

	 memcpy(cot,co,sizeof(co));

	 m=m/2;

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

 	 	{

		  scanf("%d%d",&a[i][0],&a[i][1]);

		  a[i+m][0]=a[i][1];

		  a[i+m][1]=a[i][0];

		}

	 m=m*2;

	graph_hash();

	bool ans=true;

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

		{

		 if(cot[i]!=co[i]){ans=false;break;}

		}

	 if(ans==false){printf("different\n");}

	 	else printf("same\n");

	}

 return 0;

}