大型补档计划
只有割点是必行点。
在任意一个点双中，都有分叉没有点交集的两条路径。
所以 v-DCC 缩点。
但是他问的是路径走到另一条路径的必行点。我蒙蔽了，发现自己对无向图双联通分量理解不够。因为一条边必然属于且只属于一个点双联通分量，为什么呢？因为就选这条边的两个点就构成了一个点双联通分量，所以必然存在包含的，并且由于极大性，只属于一个也显然。
缩点后变成一颗树。然后就变成了：在一颗树中，任意两点间有多少个特殊的点（割点？），用 LCA + 树上差分即可。
upd1：顺便提一句，这道题不一定保证联通，可能是森林，所以要多次dfs，但是第一次写我没多次也过了，说明数据较水。
upd2：为啥我uva WA了。
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 20005, M = 200005, L = 15;
int n, m, Q, num, newId[N];
int dfn[N], low[N], dfncnt, s[N], c[N], top, cnt, id[M], d[N];
bool vis[N];
int fa[N][L], dep[N];
vector<int> dcc[N], g[N];
bool cut[N];
int head[N], numE = 1;
struct E{
int next, v;
} e[M];
void inline add(int u, int v) {
e[++numE] = (E) { head[u], v };
head[u] = numE;
}
void tarjan(int u, int rt) {
dfn[u] = low[u] = ++dfncnt;
s[++top] = u;
if (u == rt && !head[u]) {
dcc[++cnt].push_back(u);
return;
}
int flag = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (!dfn[v]) {
tarjan(v, rt); low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) {
flag++;
if (u != rt || flag > 1) cut[u] = true;
int y; ++cnt;
do {
y = s[top--];
dcc[cnt].push_back(y);
} while (y != v);
dcc[cnt].push_back(u);
}
} else low[u] = min(low[u], dfn[v]);
}
}
void dfs(int u) {
vis[u] = true;
for (int i = 1; i < L && fa[u][i - 1]; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
if (u > cnt) d[u]++;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == fa[u][0]) continue;
fa[v][0] = u, dep[v] = dep[u] + 1, d[v] = d[u];
dfs(v);
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = L - 1; ~i; i--)
if (dep[x] - (1 << i) >= dep[y]) x = fa[x][i];
if (x == y) return x;
for (int i = L - 1; ~i; i--)
if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
int main() {
while (scanf("%d%d", &n, &m), n || m) {
for (int i = 1, x, y; i <= m; i++) {
scanf("%d%d", &x, &y);
add(x, y); add(y, x);
}
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, i);
num = cnt;
for (int i = 1; i <= n; i++) if (cut[i]) newId[i] = ++num;
for (int i = 1; i <= cnt; i++) {
for (int j = 0; j < dcc[i].size(); j++) {
int x = dcc[i][j];
if (cut[x]){
g[newId[x]].push_back(i);
g[i].push_back(newId[x]);
}
c[x] = i;
}
for (int j = 0; j < dcc[i].size(); j++) {
int x = dcc[i][j];
for (int k = head[x]; k; k = e[k].next) {
int v = e[k].v;
if (c[v] == i) id[k >> 1] = i;
}
}
}
for (int i = 1; i <= num; i++) if (!vis[i]) dfs(i);
scanf("%d", &Q);
while (Q--) {
int a, b; scanf("%d%d", &a, &b);
a = id[a], b = id[b];
int p = lca(a, b);
printf("%d
", d[fa[a][0]] - d[fa[p][0]] + d[fa[b][0]] - d[p]);
}
numE = 1;
memset(cut, false, sizeof cut);
memset(newId, 0, sizeof newId);
memset(c, 0, sizeof c);
memset(head, 0, sizeof head);
memset(dfn, 0, sizeof dfn);
memset(vis, false, sizeof vis);
memset(id, 0, sizeof id);
memset(fa, 0, sizeof fa);
for (int i = 1; i <= num; i++) g[i].clear();
for (int i = 1; i <= cnt; i++) dcc[i].clear();
dfncnt = cnt = 0;
}
return 0;
}