题目描述

给定一个 $n$ 个点 $m$ 条边的无向连通图。

$Q$ 此操作，第 $i$ 次把图上的两点 $x_i,y_i$ 连接。求每次操作后，图中的桥的数量。

输入格式

n m
u[1] v[1]
...
u[m] v[m]
Q
x[1] y[1]
...
x[Q] y[Q]

输出格式

ans[1]
...
ans[Q]

4 3
1 2
2 3
3 4
2
3 4
1 4

2
0

数据规模与约定

• 对于 $30\%$ 的数据，$1\le n,m,q \le 1000$.
• 对于 $70\%$ 的数据，$1\le n,m,q \le 2\times 10^5$.
• 对于 $100\%$ 的数据，$1\le n,m,q \le 5\times 10^6$.

（实际上我只造了 70 分的数据，满分级别一般会给定随机数据生成器和种子作为输入）

原题

http://poj.org/problem?id=3694