#include<fstream>
using namespace std;
ifstream in("rfinv.in");
ofstream out("rfinv.out");
const int NMAX = 50;
const int INFINIT = (1 << 15);

int A[NMAX + 5][NMAX + 5],V[NMAX + 5][NMAX + 5],n,m,T;
struct muchie{
    int a,b;
};
muchie v[NMAX*NMAX];

inline void init()
{

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++)
            if(i != j)
                V[i][j] = INFINIT;
}

void roy_floyd()
{
    for(int k = 1 ; k <= n ; k++)
        for(int i = 1 ;i <= n ; i++)
            for(int j = 1 ; j <= n ; j++)
                if(k != j && k != i && i != j)
                    V[i][j] = min(V[i][j],V[i][k] + V[k][j]);

}

int ok()
{

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++)
            if(V[i][j] < A[i][j])
                return 0;
    return 1;
}

void solve()
{

    for(int i = 1 ; i <= m ; i++)
        in>>v[i].a>>v[i].b;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++)
            in>>A[i][j];
    for(int i = 1 ; i <= m ; i++)
        V[v[i].a][v[i].b] = V[v[i].b][v[i].a] = A[v[i].a][v[i].b];
    roy_floyd();
    if(ok())
        out<<"DA\n";
    else
        out<<"NU\n";
}

int main()
{

    in>>T;
    for( ; T ; --T){
        in>>n>>m;
        init();
        solve();
    }
    return 0;
}