URAL/1063

来自"NOCOW"

迭代深搜

program cao;
const
  maxn=6;
 
var
  map:array[0..maxn,0..maxn] of longint;
  used,flag:array[0..maxn] of boolean;
  d,x,y:array[0..10000] of longint;
  a,b,c,e,f,g,h,i,j,k,l,n,m,p,q,ans,now:longint;
 
procedure init;
begin
  read(n);
  for i:=1 to n do
  begin
    read(a,b);
    inc(map[a,b]);
    inc(map[b,a]);
    used[a]:=true;
    used[b]:=true;
    inc(d[a]);
    inc(d[b]);
  end;
end;
 
function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;
 
function dfs(v:longint):longint;
var
  t,i:longint;
begin
  flag[v]:=true;
  t:=1;
  for i:=1 to maxn do
    if (flag[i]=false)and(map[v,i]>0) then
      t:=t+dfs(i);
  exit(t);
end;
 
function ok(depth:longint):boolean;
var
  i,j,k,l:longint;
begin
  k:=0;
  j:=0;
  for i:=1 to maxn do
    if used[i] then
    begin
      l:=i;
      break;
    end;
  for i:=i to maxn do
    if used[i] then
    begin
      inc(k);
      if odd(d[i]) then
      begin
        inc(j);
        l:=i;
        if j>2 then exit(false);
      end;
    end;
  fillchar(flag,sizeof(flag),0);
  if dfs(l)=k then exit(true)
  else exit(false);
end;
 
function search(depth:longint):boolean;
var
  i,j:longint;
begin
  if (now=ans)and(ok(depth)) then
  begin
    p:=depth-1;
    exit(true);
  end;
  for i:=x[depth-1] to maxn do
    if used[i] then
      for j:=max(y[depth-1],i+1) to maxn do
        if (used[j])and(i+j+now<=ans) then
        begin
          x[depth]:=i;
          y[depth]:=j;
          inc(d[i]);
          inc(d[j]);
          inc(map[i,j]);
          inc(map[j,i]);
          inc(now,i+j);
          if search(depth+1) then exit(true);
          dec(d[i]);
          dec(d[j]);
          dec(map[i,j]);
          dec(map[j,i]);
          dec(now,i+j);
        end;
  exit(false);
end;
 
procedure main;
begin
  ans:=0;
  x[0]:=1;
  y[0]:=1;
  while not(search(1)) do
  begin
    now:=0;
    inc(ans);
  end;
end;
 
procedure print;
begin
  writeln(ans);
  writeln(p);
  for i:=1 to p do
    writeln(x[i],‘ ‘,y[i]);
end;
 
begin
  init;
  main;
  print;
end.