记录编号	39440	评测结果	AAAAAAAAAAAAAAAAA
题目名称	[USACO Jan06]Redundant Paths	最终得分	100
用户昵称	czp	是否通过	通过
代码语言	Pascal	运行时间	0.016 s
提交时间	2012-07-11 16:09:12	内存使用	0.49 MiB

type px=^py;
    py=record
     x,y,z:longint;
     n,ag:px;
    end;
var
 i,j,m,n,f,r,xx,yy,sg,tt,mn,tp,ans:longint;
 a:array[1..5000] of px;
 o:array[1..5000] of boolean;
 st,df,low,op,ct,lx,ly:array[0..11111] of longint;
function min(xx,yy:longint):longint;
begin if xx>yy then min:=yy else min:=xx; end;
procedure add1(xx,yy:longint);
var p1:px;
begin
 new(p1);
 p1^.x:=yy;
 p1^.y:=0;
 p1^.z:=0;
 p1^.n:=a[xx];
 a[xx]:=p1;
 new(p1);
 p1^.x:=xx;
 p1^.y:=0;
 p1^.z:=0;
 p1^.n:=a[yy];
 a[yy]:=p1;
 a[xx]^.ag:=a[yy];
 a[yy]^.ag:=a[xx];
end;
procedure dfs(v:longint);
var p:px;
begin
 o[v]:=true;
 inc(sg);
 df[v]:=sg;low[v]:=sg;
 inc(tt);st[tt]:=v;
 p:=a[v];
 while p<>nil do
  begin
   if p^.z=0 then
    begin
     p^.z:=1;
     p^.y:=1;
     p^.ag^.z:=1;
     if not o[p^.x] then
      begin
       dfs(p^.x);
       low[v]:=min(low[v],low[p^.x]);
      end else low[v]:=min(low[v],df[p^.x]);
      if df[v]<low[p^.x] then begin inc(tp);lx[tp]:=v;ly[tp]:=p^.x; end;
    end;
   p:=p^.n;
  end;
 if df[v]=low[v] then
  begin
   inc(mn);
   repeat
    op[st[tt]]:=mn;
    dec(tt);
   until st[tt+1]=v;
  end;
end;
begin
 assign(input,'rpathsa.in');reset(input);
 assign(output,'rpathsa.out');rewrite(output);
 readln(f,r);
 for i:=1 to r do
  begin
   readln(xx,yy);
   add1(xx,yy);
  end;
 dfs(1);
 for i:=1 to tp do
  begin
   inc(ct[op[lx[i]]]);
   inc(ct[op[ly[i]]]);
  end;
 for i:=1 to mn do
  if ct[i]=1 then inc(ans);
 writeln((ans+1) div 2);
 close(input);close(output);
end.