1 /**************************************************  2  * Author     : xiaohao Z  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/  4  * Last modified : 2014-09-01 15:25  5  * Filename     : hdu_2460.cpp  6  * Description     :   7  * ************************************************/  8 #pragma comment(linker, "/STACK:1024000000,1024000000")  9 #include <iostream> 10 #include <cstdio> 11 #include <cstring> 12 #include <cstdlib> 13 #include <string> 14 #include <cmath> 15 #include <algorithm> 16 #include <queue> 17 #include <stack> 18 #include <vector> 19 #include <set> 20 #include <map> 21 #define MP(a, b) make_pair(a, b) 22 #define PB(a) push_back(a) 23  24 using namespace std; 25 typedef long long ll; 26 typedef pair<int, int> pii; 27 typedef pair<unsigned int,unsigned int> puu; 28 typedef pair<int, double> pid; 29 typedef pair<ll, int> pli; 30 typedef pair<int, ll> pil; 31  32 const int INF = 0x3f3f3f3f; 33 const double eps = 1E-6; 34 const int LEN = 100010; 35 vector<int> Map[LEN], tMap[LEN]; 36 stack<int> s; 37 int n, m, dclock, low[LEN], dfn[LEN], block, blong[LEN]; 38 int dep[LEN], parent[LEN], is[LEN]; 39  40 void init() 41 { 42     memset(dfn, -1, sizeof dfn); 43     memset(is, 0, sizeof is); 44     memset(parent, 0, sizeof parent); 45     dclock = is[1] = 1; block = 0; 46     while(!s.empty())s.pop(); 47     for(int i=0; i<LEN; i++) Map[i].clear(); 48 } 49  50 void dfs(int u, int fa){ 51     int v, flag = 0; 52     dfn[u] = low[u] = dclock++; 53     s.push(u); 54     for(int i=0; i<Map[u].size(); i++){ 55         v = Map[u][i]; 56         if(v==fa && !flag){flag = 1;continue;} 57         if(dfn[v]<0){ 58             dfs(v, u); 59             low[u] = min(low[u], low[v]); 60         }else if(low[u]>low[v]) low[u] = min(low[u], dfn[v]); 61     } 62     if(low[u] == dfn[u]){ 63         block ++; 64         do{ 65             v = s.top(); s.pop(); 66             blong[v] = block; 67         }while(v!=u); 68     } 69 } 70  71 void DFS(int v, int fa, int d){ 72     dep[v] = d; 73     parent[v] = fa; 74     for(int i=0; i<tMap[v].size(); i++){ 75         int x = tMap[v][i]; 76         if(x != fa)    DFS(x, v, d+1); 77     } 78 } 79  80 void build(){ 81     int a, b; 82     map<pii, int> mp; mp.clear(); 83     for(int i=0; i<LEN; i++) tMap[i].clear(); 84     for(int i=0; i<n; i++) 85         for(int j=0; j<Map[i].size(); j++){ 86             int x = Map[i][j]; 87             if(blong[i] == blong[x]) continue; 88             a = blong[i], b = blong[x]; 89             if(mp.count(MP(a, b))) continue; 90             mp[MP(a, b)] = mp[MP(b, a)] = 1; 91             tMap[a].PB(b); tMap[b].PB(a); 92         } 93     DFS(1, 0, 0); 94 } 95  96 void _(int val) {cout << "\"" << val << endl;} 97  98  99 void lca(int a, int b){100     if(dep[a] < dep[b]) swap(a, b);101     int tmp = dep[a] - dep[b];102     for(int i=0; i<tmp; i++) {103         if(!is[a]) {is[a] = 1;block --;}104         a = parent[a];105     }106     while(a != b) {107         if(!is[a]) {is[a] = 1; block --;}108         if(!is[b]) {is[b] = 1; block --;}109         a = parent[a], b = parent[b];110     }111 }112 113 int main()114 {115 //    freopen("in.txt", "r", stdin);116 117     int a, b, q, kase = 1;118     while(scanf("%d%d", &n, &m) != EOF){119         if(!n && !m) break;120         init();121         for(int i=0; i<m; i++){122             scanf("%d%d", &a, &b);123             a--, b--;124             Map[a].PB(b); Map[b].PB(a);125         }126         dfs(0, -1);127         build();128         scanf("%d", &q);129         printf("Case %d:\n", kase ++);130         for(int i=0; i<q; i++){131             scanf("%d%d", &a, &b);132             a--; b--;133             if(blong[a] != blong[b]) lca(blong[a], blong[b]);134             printf("%d\n", block - 1);135         }136         puts("");137     }138     return 0;139 }