// Infoarena. Arhiva De Probleme. Roy-Floyd Invers.

#include<iostream>
#include<fstream>
using namespace std;

void zerografiaza(int[][60],int);
void citeste_graf(int[][60],int);
void citeste_matrice(int[][60],int);
bool is_roy_floyd(int[][60],int[][60],int);

int main(){
    freopen("rfinv.in","r",stdin);
    freopen("rfinv.out","w",stdout);

    int T;
    cin>>T;
    while(T--){
        int N,M,graf[60][60],dist[60][60];
        cin>>N>>M;
       // zerografiaza(graf,N);
       for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++){
                graf[i][j]=0;
        }

       // citeste_graf(graf,M);
       int a,b;
       for(int i=1;i<=M;i++){
            cin>>a>>b;
            graf[a][b]=1;
          //  graf[b][a]=1;
       }

       // citeste_matrice(dist,M);
       for(int i=1;i<=N;i++)
           for(int j=1;j<=N;j++)
              cin>>dist[i][j];

       //check if is roy-floyd
       for(int i=1;i<=N;i++)
           for(int j=1;j<=N;j++) if(graf[i][j]) graf[i][j]=dist[i][j];

    for(int k=1;k<=N;k++)
            for(int i=1;i<=N;i++)
                for(int j=1;j<=N;j++){
                    if(i==j) continue;
                    if( (graf[i][k] && graf[j][k] && graf[i][k]+graf[k][j]<graf[i][j]) ||
                         graf[i][j]==0)
                        graf[i][j]=graf[i][k]+graf[k][j];
                }
     bool ok=true;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)
            if(graf[i][j]!=dist[i][j]){ok=false; break;};
        if(!ok) break;
        }
    if(ok) cout<<"DA\n";
    else cout<<"NU\n";


    }
}










/*
bool is_roy_floyd(int graf[60][60],int dist[60][60],int N){
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++){
            if(graf[i][j]) graf[i][j]=dist[i][j];
        }

    for(int k=1;k<=N;k++)
            for(int i=1;i<=N;i++)
                for(int j=1;j<=N;j++){
                    if(i==j) continue;
                    if(graf[i][k] && graf[j][k] && graf[i][k]+graf[k][j]<graf[i][j])
                        graf[i][j]=graf[i][k]+graf[k][j];
                }

    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++){
            if(graf[i][j]!=dist[i][j]) return false;
        }
    return true;
}

void zerografiaza(int X[60][60],int N){
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++){
            X[i][j]=0;
        }
}

void citeste_graf(int X[60][60],int M){
    int a,b;
    for(int i=1;i<=M;i++){
        cin>>a>>b;
        X[a][b]=1;
    }
}

void citeste_matrice(int X[60][60],int N){
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            cin>>X[i][j];
}
*/