SOLVE

LATER

Killjee and cities

/

Killjee lives in Codaland. Codaland has *n* cities and *m* bidirectional roads connecting these cities, but not all cities are connected. Now the President of Codaland has passed an order to build *q* new roads one by one connecting two different cities.

Killjee wonders how many new roads are needed to connect all the cities of Codaland after construction of each road as per President's plan.

**Note**:- There can be multiple number of roads between two same cities.

**INPUT FORMAT**

First line of input contain a single integer *n*, denoting number of cities.

Second line of input contains a single integer *m*, denoting number of current roads in Codaland.

Third line of input contains a single integer *s*, where \(s=2\).

*m* lines follow each having two space separated integers \(a,b\), denoting a road between city *a* and *b*.

Next line contains a single integer *q*, number of new roads to be built.

Next line of input contains a single integer *s*, where \(s=2\).

*q* lines follow each having two space separated integers \(a,b\), denoting a road between city *a* and *b*.

**OUTPUT FORMAT**

Output *q* space separated integers, \(i_{th}\) of which denotes number of roads needed to connect all the cities of Codaland after creation of first *i* roads.

**INPUT CONSTRAINTS**

\(1 \le n,q \le 10^6\)

\(0 \le m \le 10^6\)

\(1 \le a,b \le n; a!=b\)

All the roads in input are valid.

Explanation

After addition of first road between *1* and *2*, we need to connect city \(3,4\) and *5* with \((1,2)\) so, we need 3 more roads for that.

After addition of second road, the answer remains the same as cities *1* and *2* were already connected.

After addition of third road, we have cities *1* and *2* connected with each other, and cities *4* and *3* connected to each other. So, in order to connect all cities we need *2* more roads to connect *5* to \((1,2)\) and \((3,4)\).

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...