1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
| inline void add(int *h, int a, int b) { e[++ idx] = b, ne[idx] = h[a], h[a] = idx; }
void tarjan(int ver)
{
dfn[ver] = low[ver] = ++ timestamp;
stk[++ stk_top] = ver;
for (int i = h[ver]; ~i; i = ne[i])
{
int to = e[i];
if (!dfn[to])
{
tarjan(to);
low[ver] = min(low[ver], low[to]);
if (dfn[ver] == low[to])
{
int temp = 0;
++ dcc_cnt;
do {
temp = stk[stk_top --];
add(rh, dcc_cnt, temp), add(rh, temp, dcc_cnt);
} while (temp != to);
add(rh, dcc_cnt, ver), add(rh, ver, dcc_cnt);
}
}
else low[ver] = min(low[ver], dfn[to]);
}
}
void dfs1(int ver, int pre)
{
sz[ver] = 1, depth[ver] = depth[pre] + 1, fa[ver] = pre;
for (int i = rh[ver]; ~i; i = ne[i])
{
int to = e[i];
if (to == pre) continue;
dfs1(to, ver);
sz[ver] += sz[to];
if (!hson[ver] || sz[hson[ver]] < sz[to]) hson[ver] = to;
}
}
void dfs2(int ver, int topf)
{
dfn[ver] = ++ timestamp, rk[timestamp] = ver, top[ver] = topf;
if (hson[ver]) dfs2(hson[ver], topf);
for (int i = rh[ver]; ~i; i = ne[i])
{
int to = e[i];
if (to == fa[ver] || to == hson[ver]) continue;
dfs2(to, to);
}
}
struct SegsTree
{
#define lc u << 1
#define rc u << 1 | 1
struct Node { int l, r, sum; } tr[N << 2];
inline void pushup(int u) { tr[u].sum = tr[lc].sum + tr[rc].sum; }
void build(int u, int l, int r)
{
tr[u].l = l, tr[u].r = r;
if (l == r) return tr[u].sum = rk[l] <= n, void();
int mid = l + r >> 1;
build(lc, l, mid), build(rc, mid + 1, r);
pushup(u);
}
int query(int u, int l, int r)
{
if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
int mid = tr[u].l + tr[u].r >> 1, res = 0;
if (l <= mid) res += query(lc, l, r);
if (r > mid) res += query(rc, l, r);
return res;
}
} SGT;
int range_query(int x, int y)
{
int res = 0;
while (top[x] != top[y])
{
if (depth[top[x]] < depth[top[y]]) swap(x, y);
res += SGT.query(1, dfn[top[x]], dfn[x]);
x = fa[top[x]];
}
if (depth[x] > depth[y]) swap(x, y);
res += SGT.query(1, dfn[x], dfn[y]);
return res;
}
signed main()
{
memset(h, -1, sizeof h), memset(rh, -1, sizeof rh), idx = -1;
read(n, m), dcc_cnt = n;
for (int i = 1; i <= m; i ++)
{
int a, b; read(a, b);
add(h, a, b), add(h, b, a);
}
tarjan(1);
memset(dfn, 0, sizeof dfn), timestamp = 0;
dfs1(1, 0), dfs2(1, 1);
SGT.build(1, 1, dcc_cnt);
read(q);
while (q --)
{
int a, b; read(a, b);
cout << range_query(a, b) << '\n';
}
return 0;
}
|
