/*      o(N^4)      */
#include <stdio.h>
#include <algorithm>
#define N 50
#define INFI 1000000
using namespace std;
/*struct nod{
       int val,i,j;
};
struct nod x[N*N];
*/
int x[N*N],val[N*N],ii[N*N],jj[N*N];
int n,nr=0,t;
int v[N][N],d[N][N],y[N][N];
inline int min(int a,int b){  return (a>b)?b:a;   }
int compara2(int a,int b){
    return val[a]<val[b];    
}
int compara3(const void * a,const void * b){
    int *aa=(int*)a,*bb=(int*)b;
    int aaa=(int)aa,bbb=(int)bb;
    return val[aaa]-val[bbb];    
}
void start(){
    freopen("rfinv.in","r",stdin);
	freopen("rfinv.out","w",stdout);
	scanf("%d",&t);
} 
void in(){
	int i,j;
	for (i=0;i<n;++i)
		for (j=0;j<n;++j)
		    y[i][j]=0;
}
void scan(){
	int i,j,a,b,m,f;
	nr=0;
	scanf("%d%d",&n,&m);
	for (i=0;i<m;++i){
	    scanf("%d%d",&a,&b);
	    y[a-1][b-1]=1;
	    y[b-1][a-1]=1;
    }
	for (i=0;i<n;++i){
		for (j=0;j<n;++j){
			scanf("%d",&f);
			val[nr]=f;
			ii[nr]=i;
			jj[nr]=j;
			x[nr]=nr;
			++nr;
        }
   }
}
void sort(){
     sort(x,x+nr,compara2);
     //qsort(x,nr,sizeof(x[0]),compara3);
}
void init(){
	int i,j;
	for (i=0;i<n;++i){
		for (j=0;j<n;++j){
			if (i!=j)
				d[i][j]=INFI;
			else
			    d[i][j]=0;
			//printf("%d ",x[i*n+j]);
        }
        //printf("\n");
   }
   //printf("\n");
}
void solve(){
	int k,l,a,b,xx;
	for (k=0;k<nr;++k){
        xx=x[k];
        //printf("%d %d %d\n",x[k].val,x[k].i,x[k].j);
		if (d[ii[xx]][jj[xx]]>val[xx] && y[ii[xx]][jj[xx]]!=1 || d[ii[xx]][jj[xx]]<val[xx] && y[ii[xx]][jj[xx]]!=1){
           printf("NU\n");
           return;
        }
        if (d[ii[xx]][jj[xx]]>val[xx] && y[ii[xx]][jj[xx]]==1){
           d[ii[xx]][jj[xx]]=val[xx];
           for (a=0;a<n;++a)
               for (b=0;b<n;++b)
                      d[a][b]=min(d[a][b],min(d[a][ii[xx]] + val[xx] + d[jj[xx]][b], d[a][jj[xx]] + val[xx] + d[ii[xx]][b]));
        }
    }
    printf("DA\n");
}
void std_close(){
	fclose(stdin);
	fclose(stdout);
}
int main(){
	start();
    while (t--){
          in();
          scan();
	      sort();
          init();
	      solve();
    }
	std_close();
	return 0;
}