最短路------LCA+bfs

题意简洁明了， 数据级别，直接排除了多源最短路的算法，值得一提的是， 十分奇特，一棵树的边是 ，我们可以将这个图看成一棵树加上100条以内的边的图。
先考虑一棵树，如何求两点距离？我们需要前置知识点：LCA（最近公共祖先）

红色框框的两个节点u,v，求他们的距离，看他们的深度:
depth[u]=4，depth[v]=3，depth[lca]=2
细心观察，可以发现他们的树上的距离公式：

对于求LCA，方法也多种多样，倍增，树剖都是常用的主流方法，因个人喜好，影响不大。
我们解决了这个问题，那么对于多出来的100条边怎么办？（不一定是100条，其实是多出来的边数为m-n+1条，下文为了方便，一律写100条边）
我们思考一个问题：这些多出来的边，到底有没有用？
求u，v最短路的时候，对于多出来的100条边，有两种情况：
1）假设存在多出的一条边 x->y，如果从u到v最短路上，不经过x->y这条边，那么这条边不造成任何影响
2）如果经过了x->y，那么点x和点y一定都是u到v的最短路上的点，一定有 ，y同理。
所以，多出来的100条边，最多只有200个点，然后，我们直接在完整的图上对这200个点进行bfs求单源最短路。
答案已经呼之欲出了，u->v的最短路

但是！！！！！！！！！！你以为这就可以AC了吗？
直接枚举100条边的200个点进行bfs，极大可能会TLE，（啊啊啊啊！！！）
其实这200个点，是不是一定要枚举完？对于一条边x->y,我们需不需要x和y都进行一次bfs，还是只选择x或y其中一个进行bfs即可？答案当然是其中一个bfs即可啦，不然我也不会凑字数写这段话了hhhh（滑稽
为什么枚举一个即可，如果只枚举一个，会不会有错误？

按照正常来说，是不是错误只会发生在这种情况，多出来的是x->u这条边，但是我只对x进行了一次bfs，现在要求u->v的最短路，u到v的最短路等于1，而x到u的最短路+x到v的最短路=3，并不相等，是不是就错误了？？
其实并不会错，如果u到v的最短路中，不经过多出来的100条边，那么最短路就是u，v的树上距离，没有影响，如果经过了其中某些边，这些边的两个顶点都一定在这条最短路上。所以，我们只需要枚举这些边的任意一个点即可，这样就能AC了，撒花★,°:.☆(￣▽￣)/$:.°★ 。

#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define pll pair<long long, long long>
#define P pair<int, int>
#define PP pair<P, P>
#define eps 1e-10
#define PI 3.1415926535898
#define It set<node>::iterator
using namespace std;
const int INF=0x3f3f3f3f;
inline int Read() {
    int num=0;
    char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) {
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num;
}
const int maxn=1e5+150;
struct edge {
    int from,to,Next;
}Edge[maxn<<1];
int n,m,Head[maxn],tot,lg[maxn],dp[maxn][23],dep[maxn],dis[210][maxn],idx;
bool vis[maxn<<1],used[maxn<<1],pos[maxn];
void Add(int from, int to) {
    Edge[tot]={from,to,Head[from]};
    Head[from]=tot++;
    Edge[tot]={to,from,Head[to]};
    Head[to]=tot++;
}
void dfs(int u, int fa) {
    vis[u]=true;
    dep[u]=dep[fa]+1;
    dp[u][0]=fa;
    for (int i=1; i<lg[dep[u]]; i++) dp[u][i]=dp[dp[u][i-1]][i-1];
    for (int i=Head[u]; ~i; i=Edge[i].Next) {
        int v=Edge[i].to;
        if (vis[v]) continue;
        used[i]=used[i^1]=true;
        dfs(v,u);
    }
}
void bfs(int s) {
    ++idx;
    queue<int> Q;
    for (int i=0; i<=n; i++) dis[idx][i]=INF,vis[i]=false;
    Q.push(s);
    dis[idx][s]=0;
    while (!Q.empty()) {
        int u=Q.front();
        Q.pop();
        if (vis[u]) continue;
        vis[u]=true;
        for (int i=Head[u]; ~i; i=Edge[i].Next) {
            int v=Edge[i].to;
            if (dis[idx][v]>dis[idx][u]+1) {
                dis[idx][v]=dis[idx][u]+1;
                Q.push(v);
            }
        }
    }
}
int LCA(int a, int b) {
    if (dep[a]<dep[b]) swap(a,b);
    while (dep[a]>dep[b]) {
        a=dp[a][lg[dep[a]-dep[b]]-1];  
    }
    if (a==b) return a;
    for (int i=lg[dep[a]]-1; i>=0; --i) {
        if (dp[a][i]!=dp[b][i]) {
            a=dp[a][i];
            b=dp[b][i];
        }
    }
    return dp[a][0];
}
int main() {
    n=Read(),m=Read();
    Head[0]=-1;
    for (int i=1; i<=n; i++) lg[i]=lg[i-1]+(i==(1<<lg[i-1])),Head[i]=-1;
    for (int i=1; i<=m; i++) {
        int u=Read(),v=Read();
        Add(u,v);
    }
    vis[0]=true;
    dfs(1,0);
    for (int i=0; i<tot; i+=2) {
        if (used[i]) continue;
        used[i]=used[i^1]=true;
        if (!pos[Edge[i].from]) pos[Edge[i].from]=true,bfs(Edge[i].from);
//      if(!pos[Edge[i].to]) pos[Edge[i].to]=true,bfs(Edge[i].to);
    }
    int q=Read();
    while (q--) {
        int u=Read(),v=Read();
        int res=dep[u]+dep[v]-2*dep[LCA(u,v)];
        for (int i=1; i<=idx; i++) res=min(res,dis[i][u]+dis[i][v]);
        printf("%d\n",res);
    }
    return 0;
}