#include <iostream>
#include <fstream>
#define inf 10020

using namespace std;

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

int t, a[52][52],n, m, b[52][52];
//t-nr elemente ce trebuie verificate
//b-matricea drumurilor finala
//a-matricea drumurilor auxiliara
//m-nr. muchii

void initializare(){
  for(int i = 1; i < n; i++)
    for(int j = i+1; j <= n; j++)
      a[ i ][ j ] = a[ j ][ i ] = 0;
}

int minim(int a, int b){
  if(a < b)
    return a;
  return b;
}

void royFloyd(){
  for(int prin = 1; prin <= n; prin++)
    for(int din = 1; din < n; din++)
      if(a[ din ][ prin ] != 0 && din != prin)
        for(int la = din + 1; la <= n; la++)
          if(la != prin && a[ prin ][ la ] != 0){
            int temp = a[ din ][ prin ] + a[ prin ][ la ];
            a[ din ][ la ] = a[ la ][ din ] = minim(a[ din ][ la ], temp);
          }
}

void citire(){
  in>>t;
  for(int i = 1; i <= t; i++){
    in >> n >> m;
    int x, y;
    initializare();

    for(int j = 1; j <= m; j++){
      in>>x>>y;
      a[ x ][ y ] = a[ y ][ x ] = 1;
    }
    for(int j = 1; j <= n; j++)
      for(int l = 1; l <= n; l++){
        in >> b[ j ][ l ];

        if(a[ j ][ l ] == 1)
          a[ j ][ l ] = b[ j ][ l ];
        else if(j != l)
          a[ j ][ l ] = inf;
        //a e matricea drumurilor
      }
      royFloyd();
      bool ok = true;//verifica daca a e la fel cu b
      for(int j = 1; j <= n && ok == true; j++)
        for(int l = j + 1 ; l <= n; l++)
          if(a[ j ][ l ] != b[ j ][ l ]){
            ok = false;
            break;
          }
      if(ok == true)
        out << "DA\n";
      else
        out << "NU\n";
  }
}

int main(){
  citire();
  return 0;
}