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

47's Passage
No tags

Agent 47 is currently in Istanbul to complete his missions. This time agent 47 has 'N' different missions at 'N' different places in Istanbul. Diana has arranged 'M' bidirectional safe passages connecting these places, but due to some unavoidable circumstances she was not able to connect all the places via safe passages.

Due to this situation, Diana is facing a lot of anxiety and for the safety of his favorite Agent 47, she decided to arrange 'P' new safe passages one by one connecting two places in Istanbul. Due to a lot of anxiety Diana has forgotten which places are connected and which are not, so she can arrange more than one safe passages between two places.

Now, anxiety of Diana can be calculated by using the formula :

ab, where 'a' = total no. of existing safe passages and 'b' = no. of new safe passages required to connect all places in Istanbul.

Since, Agent 47 cares a lot about Diana, he wants to know anxiety of Diana after she arranges each new safe passage.

Note : See sample explanation for more Details.

Input :

  • First line contains an integer 'T', i.e the no. of test cases.
  • Second line contains two space separated integer 'N' and 'M', i.e the total no. of places in Istanbul, and the number of existing safe passages respectively.
  • 'M' lines follow, each having two space separated integer, x and y denoting there is a safe passage between place x and place y.
  • Next line contains a single integer 'P', i.e the number of new safe passages Diana decided to arrange.
  • Next 'P' lines have two space separated integers x and y, denoting a safe passage between place x and place y.

Output :

For each test case, output a new line containing 'P' space separated integers, ith of which denotes, the anxiety of Diana after arrangement of first 'i' new safe passages. Since, anxiety value can be very large so output it modulo (10^9 + 7) 1000000007.

Constraints :

  • 1<=T<=5
  • 1<=N<=106
  • 0<=M<=106
  • 1<=P<=106
  • 1<=x,y<=N
5 1
4 5
4 3
1 2
1 2
4 3 4

For the given test case :

'N'= 5 i.e there are 5 places in Istanbul. 'M'= 1 i.e. there is one safe passage and it is between place 4 and place 5. 'P'= 3, i.e Diana will arrange 3 more new safe passages. Now, first new safe passage is between place 4 and place 3, so, here,

a=2 (total no. of safe passages, one between 4 and 5, and other b/w 4 and 3)

b=2 ( two more safe passages needed to be arranged, such that all places are connected)

So, Diana's anxiety after arrangement of first new safe passage = 22 i.e. 4.

Similarly, after arrangement of safe passage between place 1 and 2, a=3,b=1; so anxiety= 31 i.e. 3.

Now, there is a safe passage b/w 1 and 2 , but they are already connected, so no. of new passages needed to connect all places i.e. 'b' will remain same, here a=4,b=1; so anxiety= 41 i.e 4

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications