#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("rfinv.in");
ofstream fout("rfinv.out");

int l[60][60],aux[60][60];
int n,m,x,y;
int van[60][60];

void royfloyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(l[i][k]!=0 && l[k][j]!=0 && i!=j && (l[i][j]>l[i][k]+l[k][j] || l[i][j]==0)) l[i][j]=l[i][k]+l[k][j];
            }
        }
    }
}

int main(){
    int t;
    fin>>t;
    for(int k=1;k<=t;k++){
        fin>>n>>m;
        for(int i=1;i<=n;i++){
            fin>>x>>y;
            van[x][y]=1;
            van[y][x]=1;
            
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                fin>>aux[i][j];
                if(van[i][j]==1) l[i][j]=aux[i][j];
            }
        }
        royfloyd();
        bool ok=true;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(aux[i][j]!=l[i][j]){ok=false;break;}
            }
            if(ok) fout<<"DA"<<endl;
            else fout<<"NU"<<endl;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                van[i][j]=0;
                l[i][j]=0;
            }
        }
    }
    return 0;
}