#include<iostream>
#include<fstream>
#define DT 35
#define DX 55
#define INF (1<<30)
using namespace std;
fstream fin("rfinv.in",ios::in),fout("rfinv.out",ios::out);
int ap[DT][DX][DX],x[DT][DX][DX],y[DT][DX][DX],bai,n;

void citire(int ind);
void roy(int ind);
void rap(int ind);

int main()
{
    int i,t;
    fin>>t;
    for(i=1;i<=t;i++)
    {
        citire(i);
        bai=0;
        roy(i);
        if(bai==0)
            fout<<"DA\n";
        else
            fout<<"NU\n";

    }
}

void roy(int ind)
{
    int i,j,k;

        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                for(k=1;k<=n;k++)
                {
                if(i!=j && x[ind][i][k] && x[ind][k][j] && (x[ind][i][j]>x[ind][i][k]+x[ind][k][j] || x[ind][i][j]==0))
                    x[ind][i][j]=x[ind][i][k]+x[ind][k][j];

            }
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            if(i!=j) if(x[ind][i][j]!=y[ind][i][j]) bai=1;
        }
    }
}

void citire(int ind)
{
    int i,j,a,b,m;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b;
        ap[ind][a][b]=ap[ind][b][a]=1;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            fin>>y[ind][i][j];
            if(ap[ind][i][j]==1) x[ind][i][j]=y[ind][i][j];
        }
}