1 /**
  2 在树中至少添加多少条边能使图变为双连通图。
  3 结论：添加边数=（树中度为1的节点数+1）/2
  4 
  5 具体方法为，首先把两个最近公共祖先最远的两个叶节点之间连接一条边，
  6 这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的
  7 环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样
  8 一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。
  9 
 10 */
 11 #include <cstdio>
 12 #include <iostream>
 13 #include <cstring>
 14 #include <algorithm>
 15 #include <cmath>
 16 #include <stack>
 17 
 18 using namespace std;
 19 const int MAXN = 5e3 + 7;
 20 const int MAXM = 1e4 + 7;
 21 
 22 struct Edge {
 23     int to, w, next;
 24     int cut;
 25 } edge[MAXM * 2];
 26 
 27 int first[MAXN], dfn[MAXN], low[MAXN], belong[MAXN], degree[MAXN], ins[MAXM];
 28 
 29 stack<int>st;
 30 
 31 int bridge; ///桥的数目
 32 
 33 int sign, n, m;
 34 
 35 int indx, scc;
 36 
 37 inline void init() {
 38     memset(first, -1, sizeof(first));
 39     sign = 0;
 40 }
 41 
 42 inline void add_edge(int u, int v, int w) {
 43     edge[sign].to = v;
 44     edge[sign].w = w;
 45     edge[sign].cut = 0;
 46     edge[sign].next = first[u];
 47     first[u] = sign++;
 48 }
 49 
 50 void tarjan(int now, int pre) {
 51     dfn[now] = low[now] = ++indx;
 52     st.push(now);
 53     ins[now] = 1;
 54     for(int i = first[now]; ~i; i = edge[i].next) {
 55         int to = edge[i].to;
 56         if(to == pre) {
 57             continue;
 58         }
 59         if(!dfn[to]) {
 60             tarjan(to, now);
 61             low[now] = min(low[now], low[to]);
 62             if(low[to] > dfn[now]) {
 63                 bridge++;
 64                 edge[i].cut = 1;
 65                 edge[i^1].cut = 1;
 66             }
 67         } else if(ins[to]) {
 68             low[now] = min(low[now], dfn[to]);
 69         }
 70     }
 71     if(dfn[now] == low[now]) {
 72         scc++;
 73         int top;
 74         do {
 75             top = st.top();
 76             st.pop();
 77             ins[top] = 0;
 78             belong[top] = scc;
 79         } while(top != now);
 80     }
 81 }
 82 
 83 int main()
 84 {
 85     int u, v;
 86     while(~scanf("%d %d", &n, &m)) {
 87         init();
 88         memset(dfn, 0, sizeof(dfn));
 89         memset(ins, 0, sizeof(ins));
 90         memset(belong, 0, sizeof(belong));
 91         memset(degree, 0, sizeof(degree));
 92         indx = scc = 0;
 93         while(!st.empty()) {
 94             st.pop();
 95         }
 96         for(int i = 1; i<= m; i++ ) {
 97             scanf("%d %d", &u, &v);
 98             add_edge(u, v, 1);
 99             add_edge(v, u, 1);
100         }
101 
102         tarjan(1, -1);
103 
104         for(int i = 1; i <= n; i++ ) {
105             for(int j = first[i]; ~j; j = edge[j].next) {
106                 int from = i, to = edge[j].to;
107                 if(edge[j].cut) {
108                     degree[ belong[i] ]++;
109                 }
110             }
111         }
112         int ans = 0;
113         for(int i = 1; i <= scc; i++ ) {
114             if(degree[i] == 1) {
115                 ans ++;
116             }
117         }
118         ans = (ans + 1) / 2;
119         printf("%d\n", ans);
120     }
121 
122     return 0;
123 }