#include <iostream>
#include <fstream>
using namespace std;
ifstream f("rfinv.in");
ofstream g("rfinv.out");
int const X=103;
int m[X][X],N,M,T;
void afis()
{
    int i,j;
    for(i=1; i<=N; i++)
    {
        for(j=1; j<=N; j++)
            g<<m[i][j]<<" ";
        g<<endl;
    }
    g<<endl;
}
int roy_warshall()
{
    int i,j,k;
    for(k=1; k<=N; k++)
        for(i=1; i<=N; i++)
            for(j=1; j<=N; j++)
                if(m[i][k] && m[k][j] && i!=j) if (m[i][k]+m[k][j]<m[i][j])  return 0;
    return 1;
}
void citire()
{
    f>>T;
    int k,j,a,b,i,x;
    for(k=1; k<=T; k++)
    {

        f>>N>>M;
        for(i=1; i<=M; i++)
        {
            f>>a>>b;
            m[a][b]=1;

        }
        for(i=1; i<=N; i++)
            for(j=1; j<=N; j++)
            {
                f>>x;
                if(x!=0) m[i][j]=x;

            }
       if(roy_warshall()) g<<"DA"<<endl;
       else g<<"NU"<<endl;
    }
}

int main()
{
    citire();

}