记录编号	39509	评测结果	AAAAAAAAAAAAAAAAA
题目名称	[USACO Jan06]Redundant Paths	最终得分	100
用户昵称	wo shi 刘畅	是否通过	通过
代码语言	Pascal	运行时间	0.019 s
提交时间	2012-07-12 20:54:48	内存使用	35.45 MiB

var
  n,m,t,total,num,top,i,j,u,v,ans,x,y:longint;
  a:array[0..1000000]of boolean;
  d,low,ru,belong,point,q,p,next,first:array[0..1000000]of longint;

procedure addpage(x,y,k:longint);
begin
  inc(total);
  point[total]:=y;
  next[total]:=first[x];
  first[x]:=total;
  p[total]:=total+k;
end;

function min(x,y:longint):longint;
begin
  if x<y then min:=x
  else min:=y;
end;

procedure tarjan(u:longint);
var
  v,i:longint;
begin
  inc(t);
  d[u]:=t;
  low[u]:=t;
  inc(top);
  q[top]:=u;
  i:=first[u];
  while i>0 do
  begin
    v:=point[i];
    if not a[i] then
    begin
      a[i]:=true;
      a[p[i]]:=true;
      if d[v]=0 then
      begin
        tarjan(v);
        low[u]:=min(low[u],low[v]);
      end
      else low[u]:=min(low[u],d[v]);
    end;
    i:=next[i];
  end;

  if d[u]=low[u] then
  begin
    inc(num);
    repeat
      v:=q[top];
      belong[v]:=num;
      dec(top);
    until v=u;
  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);
    addpage(x,y,1);
    addpage(y,x,-1);
  end;
  tarjan(1);
  for u:=1 to n do
  begin
    i:=first[u];
    while i>0 do
    begin
      v:=point[i];
      if belong[u]<>belong[v] then
      begin
        inc(ru[belong[u]]);
        inc(ru[belong[v]]);
      end;
      i:=next[i];
    end;
  end;
  ans:=0;
  for i:=1 to num do
  if ru[i]=2 then inc(ans);
  writeln((ans+1) div 2);
  close(input);
  close(output);
end.