记录编号	39459	评测结果	AAAAAAAAAAAAAAAAA
题目名称	[USACO Jan06]Redundant Paths	最终得分	100
用户昵称	zhangchi	是否通过	通过
代码语言	Pascal	运行时间	0.017 s
提交时间	2012-07-11 17:51:02	内存使用	0.55 MiB

type
  node=record
         v,next,un:longint;
         p:boolean;
       end;
var
  n,m,i,j,ans,num,tot,x,y,stamp,t,top:longint;
  f:array[1..5000] of longint;
  a:array[1..20000] of node;
  stack:array[1..5000] of longint;
  mark:array[1..5000] of longint;
  du:array[1..5000] of longint;
  low,dfn:array[1..5000] of longint;
  q:array[1..5000] of boolean;
  function min(x,y:longint):longint;
  begin if x<y then min:=x else min:=y; end;
  procedure insert(x,y:longint);
  begin
    inc(tot);
    a[tot].next:=f[x];
    f[x]:=tot;
    a[tot].v:=y;
    a[tot].p:=false;
    a[tot].un:=tot+1;
    inc(tot);
    a[tot].next:=f[y];
    f[y]:=tot;
    a[tot].v:=x;
    a[tot].p:=false;
    a[tot].un:=tot-1;
  end;
  procedure tarjan(x:longint);
  var
    t:longint;
  begin
    inc(stamp);
    low[x]:=stamp;
    dfn[x]:=stamp;
    inc(top);
    stack[top]:=x;
    q[x]:=true;
    t:=f[x];
    while t<>0 do
      begin
        if a[t].p=false then
          begin
            a[t].p:=true;
            a[a[t].un].p:=true;
            if q[a[t].v]=false then
              begin
                tarjan(a[t].v);
                low[x]:=min(low[x],low[a[t].v]);
              end
              else low[x]:=min(low[x],dfn[a[t].v]);
          end;
        t:=a[t].next;
      end;
    if low[x]=dfn[x] then
      begin
        inc(num);
        repeat
          mark[stack[top]]:=num;
          dec(top);
        until stack[top+1]=x;
      end;
  end;
begin
  assign(input,'rpathsa.in'); reset(input);
  assign(output,'rpathsa.out'); rewrite(output);
  readln(n,m);
  for i:=1 to m do
    begin
      readln(x,y);
      insert(x,y);
    end;
  tarjan(1);
  for i:=1 to n do
    begin
      t:=f[i];
      while t<>0 do
        begin
          if mark[i]<>mark[a[t].v] then
            begin
              inc(du[mark[i]]);
              inc(du[mark[a[t].v]]);
            end;
          t:=a[t].next;
        end;
    end;
  for i:=1 to num do
    if du[i]=2 then inc(ans);
  writeln((ans+1) div 2);
  close(input); close(output);
end.