program hungarian;Type rec=record   e,next:longint; end;Var a:array[0..200] of rec; b,last:array[0..100] of longint;//last表示每个节点在匹配中的对应节点是什么，last[i]=0表示i是未盖点 n,m,i,st,ed,ans,top:longint; v:array[0..100] of boolean;//表示在“每一轮增广”中某个节点有没有访问过Procedure add(st,ed:longint);  begin  inc(top);  with a[top] do    begin    e:=ed;    next:=b[st];  end;  b[st]:=top;end;function dfs(P:longint):boolean;//P下一条总是要找非匹配边var u:longint; y:^rec;  begin  dfs:=false;  u:=b[p];  while u<>b[0] do    begin    y:=@a[u];    u:=y^.next;    if not v[y^.e] then //如果某一个点之前已被访问过表示其已经增广，没有必要再访问      begin      v[y^.e]:=true;      if (last[y^.e]=0) or dfs(last[y^.e]) then //y^.e是未盖点，直接连一条，继续找非匹配边；y^.e是已盖点，先连非匹配边 P - y^.e 再连匹配边 y^.e - last[y^.e] ，之后只要判断dfs(last[y^.e])即可        begin        last[y^.e]:=p;        last[p]:=y^.e;        exit(true);      end;    end;  end;  exit(false);end;  begin  readln(n,m);  fillchar(b,sizeof(b),$ff);top:=-1;  for i:=1 to m do    begin    readln(st,ed);    add(st,ed);    add(ed,st);  end;  ans:=0;  for i:=1 to n do    if last[i]=0 then //从未盖点开始增广，但是没有这一行经测试也行= =暂时不知道为什么      begin      fillchar(v,sizeof(v),false); //每一轮清空v数组      inc(ans,ord(dfs(i)));  //每增广一次ans++    end;  writeln(ans);end.

 附赠一组数据：

Input

6 22

1 7

1 8

1 9

1 11

2 7

2 8

2 12

3 7

3 8

3 9

3 10

3 12

4 7

4 8

4 9

4 12

5 7

5 10

5 12

6 9

6 11

6 12

Output

6

匹配边

1 10

2 8

3 7

4 9

5 12

6 11