All Tracks Data Structures Disjoint Data Structures Basics of Disjoint Data Structures Problem

Killjee and cities
/

Data Structures, Disjoint set, Graphs

Problem
Editorial
Analytics

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.

SAMPLE INPUT
5
0
2
3
2
2 1
2 1
4 3
SAMPLE OUTPUT
3 3 2
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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?