var v,c,p:array[1..51,1..51]of longint;
    n,i,j,k,l,t,m,a,b,f:longint;
    f1,f2:text;
begin
   assign(f1,'rfinv.in');
   reset(f1);
   assign(f2,'rfinv.out');
   rewrite(f2);
   read(f1,t);
   for l:=1 to t do
   begin
   for i:=1 to 50 do
   for j:=1 to 50 do
   begin
   c[i,j]:=0;
   v[i,j]:=0;
   p[i,j]:=0;
   end;
   f:=0;
   read(f1,n,m);
   for i:=1 to m do
   begin
   read(f1,a,b);
   p[a,b]:=1;
   p[b,a]:=1;
   end;
   for i:=1 to n do
   for j:=1 to n do
   begin
   read(f1,v[i,j]);
   if v[i,j]=0 then v[i,j]:=10000000;
   if p[i,j]=1 then c[i,j]:=v[i,j]
               else c[i,j]:=10000000;
   end;
   for k:=1 to n do
   for i:=1 to n do
   for j:=1 to n do
   if(i<>k)and(j<>k)and(i<>j)and(c[i,k]+c[k,j]<c[i,j])and(c[i,k]>0)and(c[k,j]>0)then begin c[i,j]:=c[i,k]+v[k,j];
                                                                                           c[j,i]:=c[i,k]+v[k,j];
                                                                                     end;
   for i:=1 to n do
   for j:=1 to n do
   if c[i,j]<>v[i,j] then f:=1;
   if f=1 then writeln(f2,'NU')
          else writeln(f2,'DA');
   end;
   close(f1);
   close(f2);
end.