记录编号	9939	评测结果	AAATTTTTTT
题目名称	[AHOI2006] 棋盘上的问题	最终得分	30
用户昵称	苏轼	是否通过	未通过
代码语言	Pascal	运行时间	71.576 s
提交时间	2009-04-22 20:42:00	内存使用	10.11 MiB

{
 haoi2009 moni2 t3
 hangry
 time:2009.4.22
}
program cch(input,output);
type
 edge=record
       next,p:longint;
       b:boolean;
      end;
var
 fx,fy,v:array[1..200000] of longint;
 e:array[1..600000] of edge;
 tot,n,m,ch:longint;
 flag:array[1..200000] of longint;

procedure ins(x,y:longint);
var
 i:longint;
begin
 inc(tot); e[tot].next:=0; e[tot].p:=y;
 e[tot].b:=true;
 if v[x]=0 then v[x]:=tot
  else
   begin
    i:=v[x];
    while e[i].next<>0 do
     i:=e[i].next;
    e[i].next:=tot;
   end;
end;

procedure init;
var
 i,y,x:longint;
begin
 assign(input,'board.in');
 assign(output,'board.out');
 reset(input);
 rewrite(output);
 readln(n,m);
 tot:=0;
 for i:=1 to m do
  begin
   readln(x,y);
   ins(x,y);
  end;
end;

function dfs(x:longint):boolean;
var
 i:longint;
begin
 i:=v[x];
 while i<>0 do
  begin
   if (flag[e[i].p]<>ch) and e[i].b then
    begin
     flag[e[i].p]:=ch;
     if (fy[e[i].p]=-1)or(dfs(fy[e[i].p])) then
      begin
       fx[x]:=e[i].p; fy[e[i].p]:=x;
       exit(true);
      end;
    end;
   i:=e[i].next;
  end;
 exit(false);
end;

procedure main;
var
 ans1,ans2,ans,i,j,k:longint;
 tmp1,tmp2:array[1..200000] of longint;
begin
 for i:=1 to n do fx[i]:=-1;
 for i:=1 to n do fy[i]:=-1;
 for i:=1 to n do flag[i]:=0;
 ans1:=0; ch:=0;
 for i:=1 to n do
  if fx[i]=-1 then
   begin
    inc(ch);
    if dfs(i) then inc(ans1);
   end;
 ans:=tot-ans1;
 for i:=1 to n do
  if fx[i]<>-1 then
   begin
    j:=v[i]; k:=0;
    while j<>0 do
     begin
      if e[j].p=fx[i] then
       begin
        k:=j;
        break;
       end;
      j:=e[j].next;
     end;
    e[k].b:=false;
    ans2:=0;
    for j:=1 to n do tmp1[j]:=fx[j];
    for j:=1 to n do tmp2[j]:=fy[j];
    for j:=1 to n do fx[j]:=-1;
    for j:=1 to n do fy[j]:=-1;
    for j:=1 to n do
     if fx[j]=-1 then
      begin
       inc(ch);
       if dfs(j) then inc(ans2);
      end;
    for j:=1 to n do fx[j]:=tmp1[j];
    for j:=1 to n do fy[j]:=tmp2[j];
    if ans2=ans1 then inc(ans);
    e[k].b:=true;
  end;
 writeln(ans);
 close(input);
 close(output);
end;

begin
 init;
 main;
end.