1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstring>

 4 #include <cmath>

 5 #include <algorithm>

 6 #include <string>

 7 #include <vector>

 8 #include <set>

 9 #include <map>

10 #include <stack>

11 #include <queue>

12 #include <sstream>

13 #include <iomanip>

14 using namespace std;

15 typedef long long LL;

16 const int INF = 0x4fffffff;

17 const double EXP = 1e-5;

18 const int MS = 105;

19 const int SIZE = 100005;

20

21 //  求无向图的顶点连通度    最大流算法

22

23 int cap[MS][MS];

24 int flow[MS][MS];        //将struct c  f  拆开成两个数组

25 int que[MS];

26 int pre[MS];

27 int alpha[MS];

28 int qs,qe,nodes;

29 int n,m;

30

31 int max_flow(int source ,int sink)

32 {

33       memset(flow,0,sizeof(flow));   // 0流 开始增加流量

34       int res=0;

35       while(1)

36       {

37             qs=qe=0;

38             que[qe++]=source;

39             memset(pre,-1,sizeof(pre));   //  pre可以同时起到flag的作用

40             memset(alpha,-1,sizeof(alpha));

41             alpha[source]=INF;

42             pre[source]=-2;   //  -2  结束标记，同时又避免了-1,表示未访问

43             while(qs<qe)

44             {

45                   int u=que[qs++];

46                   for(int v=0;v<nodes;v++)

47                   {

48                         if(pre[v]==-1&&flow[u][v]<cap[u][v])

49                         {

50                               que[qe++]=v;

51                               pre[v]=u;

52                               alpha[v]=min(alpha[u],cap[u][v]-flow[u][v]);

53                         }

54                   }

55                   if(pre[sink]!=-1)

56                   {

57                         int k=sink;

58                         while(pre[k]>=0)

59                         {

60                               flow[pre[k]][k]+=alpha[sink];

61                               flow[k][pre[k]]=-flow[pre[k]][k];

62                               k=pre[k];

63                         }

64                         break;

65                   }

66             }

67             if(pre[sink]==-1)        //不存在增广路

68                   return res;

69             else

70                   res+=alpha[sink];

71       }

72 }

73

74 int main()

75 {

76       while(scanf("%d%d",&n,&m)!=EOF)

77       {

78             int a,b,ans=INF;

79             memset(cap,0,sizeof(cap));

80             nodes=2*n;

81             for(int i=0;i<n;i++)

82                   cap[i][i+n]=1;

83             for(int i=0;i<m;i++)

84             {

85                   scanf(" (%d,%d)",&a,&b);

86                   cap[a+n][b]=cap[b+n][a]=INF;

87             }

88             for(int v=1;v<n;v++)

89             {

90                   ans=min(ans,max_flow(n,v));

91             }

92             if(ans==INF)

93                   ans=n;

94             printf("%d\n",ans);

95       }

96       return 0;

97 }