#include <fstream>
using namespace std;

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

const int MAXN = 55, INF = 10009;

int N, M, T, d[MAXN][MAXN], dist[MAXN][MAXN];

inline void initializare()
{
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            d[i][j] = INF;
}

inline void citire()
{
    int a, b;

    fin >> N >> M;
    initializare();
    for (int i = 0; i < M; ++i)
    {
        fin >> a >> b;
        d[a][b] = d[b][a] = 0;
    }

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            fin >> dist[i][j];

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if ( d[i][j] == 0 )
                d[i][j] = dist[i][j];
}

inline void RoyFloyd()
{
    for (int k = 1; k <= N; ++k)
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                if ( d[i][k] + d[k][j] < d[i][j] )
                    d[i][j] = d[i][k] + d[k][j];
}

inline bool compara()
{
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j)
            if ( d[i][j] != dist[i][j] && i != j )
                return false;
    return true;
}

int main ()
{
    fin >> T;
    for (int i = 0; i < T; ++i)
    {
        citire();
        RoyFloyd();
        if ( compara() )
            fout << "DA\n";
        else
            fout << "NU\n";
    }

    fin.close();
    fout.close();

    return 0;
}