{ NEERC'98 Problem "Defragment"
  Checking program by Roman Elizarov
  20.11.98
}
{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
program DEFRAGMENT_CHECK;
uses
  testlib;

function IsNoOpt ( s: string ): boolean;
begin
  IsNoOpt:= s = 'No optimization needed';
end;

const
  maxn = 10000;

var
  n, k, s, i, j, cnt, cl: integer;
  lines_ans, lines_ouf: longint;
  dest: array[1..maxn] of integer;
  p, q: longint;
  wa: boolean;
  wmsg: string;

begin
 { read input }
  n:= inf.readLongint;
  k:= inf.readLongint;
  fillchar(dest, sizeof(dest), 0);
  cnt:= 0;
  for i:= 1 to k do begin
    s:= inf.readLongint;
    for j:= 1 to s do begin
      inc(cnt);
      cl:= inf.readLongint;
      dest[cl]:= cnt;
    end;
  end;

  if IsNoOpt ( ans.readString ) then
    lines_ans:= 0
  else begin
    lines_ans:= 1;
    while not ans.seekeof do begin
      inc ( lines_ans );
      ans.nextLine;
    end;
  end;

  lines_ouf:= 0;
  ouf.skip ( NumberBefore );
  wa:= false;
  if ouf.curchar in ['0'..'9'] then begin
    while not ouf.seekeof do begin
      p:= ouf.readLongint;
      q:= ouf.readLongint;
      if not ouf.seekeoln then
        QUIT ( _PE, 'Extra data on line' );
      inc ( lines_ouf );
      if wa then
        continue;
      if (p < 1) or (p > n) then begin
        wa:= true;
        wmsg:= 'Cluster is out of range: ';
        continue;
      end;
      if (q < 1) or (q > n) then begin
        wa:= true;
        wmsg:= 'Cluster is out of range: ';
        continue;
      end;
      if dest[p] = 0 then begin
        wa:= true;
        wmsg:= 'Cluster is not occupied: ';
        continue;
      end;
      if dest[q] <> 0 then begin
        wa:= true;
        wmsg:= 'Cluster is not free: ';
        continue;
      end;
      dest[q]:= dest[p];
      dest[p]:= 0;
    end;
  end else begin
    if not IsNoOpt ( ouf.readString ) then
      QUIT ( _PE, 'Message is wrong?' );
    if not ouf.seekeof then
      QUIT ( _PE, 'Extra data in output' );
  end;

  if wa then
    QUIT ( _WA, wmsg );

  for i:= 1 to n do
    if (dest[i] <> 0) and (dest[i] <> i) then
      QUIT ( _WA, 'Not optimal: ' );

  if lines_ouf <> lines_ans then
    QUIT ( _WA, 'Not minimal: ');

  QUIT ( _OK, 'Ok' );
end.

