#include <iostream>
#include <fstream>

using namespace std;

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

struct laturi
{
    int a, b;
}v[1226];
int a[51][51], cost[51][51];
const int INFINIT=12250001;
int main()
{
    int t, y, n, m, k, i, j;
    bool ok;
    fin>>t;

    for(y=1; y<=t; y++)
    {
        fin>>n>>m;
        for(i=1; i<=m; i++)
        {
            fin>>v[i].a>>v[i].b;
        }
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                fin>>a[i][j];
            }
        }
        ok=1;
        for(i=1; i<=n; i++)
        {
            for(j=i; j<=n; j++)
            {
                if(a[i][j]!=a[j][i])
                {
                    ok=0;
                }
            }
        }
        if(ok==0)
        {
            fout<<"NU\n";
        }
        else
        {
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                if(i!=j)cost[i][j]=INFINIT;
                else cost[i][j]=0;
            }
        }
        for(i=1; i<=m; i++)
        {
            cost[ v[i].a ][ v[i].b ]=cost[ v[i].b ][ v[i].a ]=a[ v[i].a ][ v[i].b ];
        }
        for(k=1; k<=n; k++)
        {
            for(i=1; i<=n; i++)
            {
                for(j=1; j<=n; j++)
                {
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
                }
            }
        }
        ok=1;
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                if(cost[i][j]==INFINIT) cost[i][j]=0;
                if(cost[i][j]!=a[i][j])
                {
                    ok=0;
                    break;
                }
            }
        }
        if(ok) fout<<"DA\n";
        else fout<<"NU\n";
        }
    }


}