记录编号	39461	评测结果	AAAAAAAAAAAAAAAAA
题目名称	[USACO Jan06]Redundant Paths	最终得分	100
用户昵称	fuhao	是否通过	通过
代码语言	Pascal	运行时间	0.022 s
提交时间	2012-07-11 18:03:25	内存使用	0.67 MiB

program rpathsa;
const maxn=5001; maxm=30000;
var
 num,a,dfn,low,fa:array[0..maxn] of longint;
 next,link,un:array[0..maxm] of longint;
 bridge,vv:array[0..maxm] of boolean;
 v:array[0..maxn] of boolean;
 index,i,j,f,r,x,y,ans,tot,n,top:longint;
 procedure insert(x,y:longint);
 begin
  inc(tot); next[tot]:=a[x]; a[x]:=tot;
  link[tot]:=y; un[tot]:=tot+1;
  inc(tot); next[tot]:=a[y]; a[y]:=tot;
  link[tot]:=x; un[tot]:=tot-1;
 end;
 procedure tarjan(k,fa:longint);
 var i:longint;
 begin
  v[k]:=true;
  inc(index); dfn[k]:=index; low[k]:=index;
  i:=a[k];
  while i<>0 do
   begin
    if not v[link[i]] then
     begin
      vv[i]:=true; vv[un[i]]:=true;
      tarjan(link[i],k);
      if low[k]>low[link[i]] then low[k]:=low[link[i]];
      if dfn[k]<low[link[i]] then
       begin
        bridge[i]:=true;
        bridge[un[i]]:=true;
       end;
     end else
     if (link[i]<>fa) or (not vv[i]) and (fa=link[i]) and (not vv[un[i]]) then
     if low[k]>dfn[link[i]] then low[k]:=dfn[link[i]];
    vv[i]:=true; vv[un[i]]:=true;
    i:=next[i];
   end;
 end;
 procedure dfs(k,s:longint);
 var i:longint;
 begin
  v[k]:=true; fa[k]:=s;
  i:=a[k];
  while i<>0 do
   begin
    if not bridge[i] then
     if not v[link[i]] then
       dfs(link[i],s);
    i:=next[i];
   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(x,y);
   insert(x,y);
  end;
 tarjan(1,0);
 fillchar(v,sizeof(v),#0);
 for i:=1 to f do
  if not v[i] then dfs(i,i);
 ans:=0;
 for i:=1 to f do
  begin
   j:=a[i];
   while j<>0 do
    begin
     if bridge[j] then
      begin
       bridge[un[j]]:=false;
       inc(num[fa[i]]); inc(num[fa[link[j]]]);
      end;
     j:=next[j];
    end;
  end;
 for i:=1 to f do
  if num[i]=1 then ans:=ans+1;
 writeln((ans+1) div 2);
 close(input); close(output);
end.