ZZXYY's blog

const
  maxe=50000;
  maxn=1000;
  inf=2147483647;
type
  edge=record
         x,y,next,op:longint;
       end;
var
  e:array[0..maxe]of edge;
  a,gap,dis,pre,cur:array[0..maxn]of longint;
  n,m,i,j,k,l,s,t,u,v,cap,flow,mf:longint;
  ee:array[1..maxn,1..maxn]of longint;
procedure adde(u,v,cap,cc:longint);
var
  i:longint;
begin
  inc(l);
  e[l].y:=cap;
  e[l].x:=v;
  e[l].next:=a[u];
  e[l].op:=l+1;
  a[u]:=l;
  inc(l);
  e[l].y:=cc;
  e[l].x:=u;
  e[l].op:=l-1;
  e[l].next:=a[v];
  a[v]:=l;
end;
function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;
procedure sap;
var
  i,j,k,now,p,pp,dist:longint;
  f:boolean;
begin
  fillchar(dis,sizeof(dis),0);
  fillchar(gap,sizeof(gap),0);
  for i:=s to t do cur[i]:=a[i];
  mf:=0;
  now:=s;
  gap[t]:=t;
  flow:=inf;
  while dis[s]<=t do
  begin
    if now=t then
    begin
      flow:=inf;
      i:=s;
      while i<>t do
      begin
        flow:=min(flow,e[cur[i]].y);
        i:=e[cur[i]].x;
      end;
      i:=s;
      while i<>t do
      begin
        dec(e[cur[i]].y,flow);
        inc(e[e[cur[i]].op].y,flow);
        i:=e[cur[i]].x;
      end;
      mf:=mf+flow;
      now:=s;
    end;
    p:=cur[now];
    f:=true;
    while p<>0 do
    begin
      pp:=e[p].x;
      if (e[p].y>0) and (dis[now]=dis[pp]+1) then
      begin
        cur[now]:=p;
        pre[pp]:=now;
        now:=pp;
        f:=false;
        break;
      end;
      p:=e[p].next;
    end;
    if f then
    begin
      dec(gap[dis[now]]);
      if gap[dis[now]]=0 then break;
      cur[now]:=a[now];
      p:=a[now];
      dis[now]:=t+1;
      while p<>0 do
      begin
        pp:=e[p].x;
        if (e[p].y>0) then dis[now]:=min(dis[pp]+1,dis[now]);
        p:=e[p].next;
      end;
      inc(gap[dis[now]]);
      if now<>s then now:=pre[now];
    end;
  end;
end;
begin
  read(n,m);
  s:=0;
  t:=n*2+1;
  for i:=1 to n do
  begin
    adde(s,i,1,0);
    adde(i+n,t,1,0);
  end;
  for i:=1 to m do
  begin
    read(u,v);
    ee[u,v]:=1;
  end;
  for i:=1 to n do
  for j:=1 to n do
  if i<>j then
  for k:=1 to n do
  if (i<>k) and (j<>k) then
  if (ee[i,k]=0) and (ee[i,j]=1) and (ee[j,k]=1) then ee[i,k]:=1;
  for i:=1 to n do
  for j:=1 to n do
  if (i<>j) and (ee[i,j]=1) then
  adde(i,j+n,1,0);
  sap;
  writeln(n-mf);
end.