401876: GYM100551 B GraphAero

Given an undirected graph with N vertices's and M edges. You are to process K queries of adding new edges into the graph. After each query you should output the only number - amount of bridges in graph. Graph may contain loops and multiple edges.

The first line of input contains two integers N and M: the number of vertices and edges, respectively. 1 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁵. The following M lines contain edges, one per line. Two integers a_i and b_i follow, describing the edge. 1 ≤ a_i, b_i ≤ N.

The next line of input contains only integer K: the number of requests. 1 ≤ K ≤ 10⁵. The following K lines contain requests, one per line. Two integers a_i and b_i follow, describing the edge to add. 1 ≤ a_i, b_i ≤ N.

Write K integers: the number of bridges in the graph after each request.

4 0
4
1 2
2 3
3 4
1 4

1
2
3
0