#include <fstream>

using namespace std;

ifstream f("rfinv.in");
ofstream g("rfinv.out");

int n,m,a[1500][1500],t,x,y,i,j,j1,j2,aa[1500][1500];
bool ans;

void drum(int i, int j)
{
    int k=1,gasit=0;
    while((k<=n) && !gasit)
    {
        if(i!=k && j!=k && a[i][j]==a[i][k]+a[k][j])
        {
            drum(i,k);
            drum(k,j);
            gasit=1;
        }
        k++;
    }
}

void length()
{
    int i,j,k;
    for(k=1; k<=n; k++)
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                if(a[i][j]>a[i][k]+a[k][j])
                    a[i][j]=a[i][k]+a[k][j];
}



int main()
{
    f >> t;
    for(; t>=1; --t)
    {
        f >> n >> m;
        for(i=1; i<=m; i++)
            f >> x >> y;
        for(j1=1;j1<=n;j1++){
        for(j2=1;j2<=n;j2++)
                f >> a[j1][j2];
                }

        for(j1=1;j1<=n;j1++)
        for(j2=1;j2<=n;j2++)
            aa[j1][j2]=a[j1][j2];

        length();

        ans=true;

        for(j1=1;j1<=n;j1++)
        for(j2=1;j2<=n;j2++)
                if(a[j1][j2]!=aa[j1][j2])
                    {
                        ans=false;
                        break;
                        }


        if(ans==true) g << "DA" << '\n';
        else g << "NU" << '\n';

                }

        f.close();
        g.close();

        return 0;
    }