ac1137.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1137;
const
  maxn=20;
var
  e:array[1..maxn,1..maxn]of integer;
  q,lv,r1,r2:array[1..maxn]of byte;
  loop:array[1..maxn]of boolean;
  t,u,n,m,i,f,r,count,bad:longint;
  first:boolean;
function multi(x:word):boolean;
  begin
    for f:=2 to n do
      if e[x,f]>1 then begin
        multi:=true;exit;
      end;
    multi:=false;
  end;
begin
  read(t);
  for u:=1 to t do begin
    fillchar(e,sizeof(e),0);
    fillchar(r1,sizeof(r1),0);
    fillchar(loop,sizeof(loop),0);
    read(n,m);
    for i:=1 to m do begin
      read(f,r);dec(e[f,r]);dec(e[r,f]);
    end;

    f:=0;r:=1;q[1]:=1;r1[1]:=1;
    repeat
      inc(f);
      for i:=2 to n do
        if e[q[f],i]<0 then begin
          e[q[f],i]:=-e[q[f],i];e[i,q[f]]:=-e[i,q[f]];
          if r1[i]=0 then begin
            inc(r);q[r]:=i;lv[i]:=lv[q[f]]+1;
            case lv[i] of
              1:r1[i]:=i;
              2:begin r1[i]:=q[f];r2[i]:=i;end;
              else begin r1[i]:=r1[q[f]];r2[i]:=r2[q[f]];end;
            end;
          end
          else if r1[q[f]]<>r1[i] then
            loop[1]:=true
          else if r2[q[f]]<>r2[i] then
            loop[r1[i]]:=true;
        end;
    until f=r;

    if (r=1) or loop[1] then
      bad:=0
    else begin
      count:=0;bad:=1;
      for i:=2 to n do
        if e[1,i]>1 then begin
          inc(count);
          if (count=2) or loop[i] or multi(i) then begin bad:=0;break;end;
          if not odd(e[1,i]) then bad:=i;
        end;
    end;

    first:=true;
    for i:=1 to n do
      if (r1[i]>0) and (i<>bad) then begin
        if first then first:=false else write(' ');
        write(i);
      end;
    writeln;
  end;
end.