圆方树，TLE70分，求卡

也许我树链剖分写假了？

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std;

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int qread() {
	register char c = getchar();
	register int x = 0, f = 1;
	while (c < '0' || c > '9') {
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + c - 48;
		c = getchar();
	}
	return x * f;
}

inline int Abs(const int& x) {return (x > 0 ? x : -x);}
inline int Max(const int& x, const int& y) {return (x > y ? x : y);}
inline int Min(const int& x, const int& y) {return (x < y ? x : y);}

struct Edge {
	int to, nxt;
	Edge() {
		nxt = -1;
	}
};
struct Graph {
	int hd[1000005], pnt;
	Edge e[4000005];
	Graph() {
		memset(hd, -1, sizeof(hd));
		pnt = 0;
	}
	inline void AddEdge(int u, int v) {
		//printf("%d<->%d\n", u, v);
		e[++pnt].to = v;
		e[pnt].nxt = hd[u];
		hd[u] = pnt;
	}
};
int n, m, dfn[500005], low[500005], _time, bcccnt, dep[1000005], siz[1000005], son[1000005], top[1000005], fa[1000005];
Graph reg, rst;
stack <pair <int, int> > stk;

inline void Read() {
	n = qread(); m = qread();
	for (register int i = 1;i <= m;i++) {
		register int u = qread(), v = qread();
		reg.AddEdge(u, v);
		reg.AddEdge(v, u);
	}
}

inline void Tarjan(int u, int fa) {
	dfn[u] = low[u] = ++_time;
	for (register int i = reg.hd[u];~i;i = reg.e[i].nxt) {
		register int v = reg.e[i].to;
		if (!dfn[v]) {
			stk.push(make_pair(u, v));
			Tarjan(v, u);
			low[u] = Min(low[u], low[v]);
			if (low[v] >= dfn[u]) {
				bcccnt++;
				while (1) {
					register int x = stk.top().first, y = stk.top().second;
					stk.pop();
					rst.AddEdge(y, bcccnt + n);
					rst.AddEdge(bcccnt + n, y);
					if (x == u && y == v) {
						rst.AddEdge(x, bcccnt + n);
						rst.AddEdge(bcccnt + n, x);
						break;
					}
				}
			}
		} else if (dfn[v] < dfn[u] && v != fa) {
			stk.push(make_pair(u, v));
			low[u] = Min(low[u], dfn[v]);
		}
	}
}

inline void Dfs1(int u) {
	siz[u] = 1;
	register int mx = 0;
	for (register int i = rst.hd[u];~i;i = rst.e[i].nxt) {
		if (rst.e[i].to != fa[u]) {
			fa[rst.e[i].to] = u;
			dep[rst.e[i].to] = dep[u] + 1;
			Dfs1(rst.e[i].to);
			siz[u] += siz[rst.e[i].to];
			if (siz[rst.e[i].to] > mx) {
				mx = siz[rst.e[i].to];
				son[u] = rst.e[i].to;
			}
		}
	}
}

inline void Dfs2(int u, int tp) {
	top[u] = tp;
	if (son[u]) Dfs2(son[u], tp);
	for (register int i = rst.hd[u];~i;i = rst.e[i].nxt) {
		if (rst.e[i].to != son[u] && rst.e[i].to != fa[u]) Dfs2(rst.e[i].to, rst.e[i].to);
	}
}

inline int Lca(int u, int v) {
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		u = fa[top[u]];
	}
	if (dep[u] < dep[v]) return u;
	else return v;
}

inline void Solve() {
	register int q = qread();
	while (q--) {
		register int u = qread(), v = qread();
		register int dis = dep[u] + dep[v] - (dep[Lca(u, v)] << 1);
		printf("%d\n", (dis >> 1) + 1);
	}
}

int main() {
	Read();
	Tarjan(1, -1);
	dep[1] = 1;
	Dfs1(1);
	Dfs2(1, 1);
	Solve();
	#ifndef ONLINE_JUDGE
	while (1);
	#endif
	return 0;
}