SP17789 SPACEBRG - Space Bridges

**Space Bridges** A long time ago, in a galaxy far, far away…. war is going on between the Galactic Empire and the Rebel Alliance. During wars like these, space bridges are really resourceful as they can transfer almost anything including Storm Trooper armies from one space region to another in just mere seconds. Each space region consists of many sectors. The sectors are connected with each other via space roads in such a way that there is exactly one path from one sector to another within a space region. Note that space roads and space bridges are not the same. The sectors of two space regions of the empire have already been arranged. To find if the arrangement is strong enough, the Supreme _Commander_ of the Imperial Forces has ordered you, their top programmer to calculate the total strength of the two regions.  Two regions can be connected using exactly one Space Bridge from one sector of a region to one sector of the other region. The value of a space bridge connection is the maximum path length you need to travel from any sector of one region to any sector of the other region using any space road or space bridge at most once. The total strength of two regions is the summation of the power of all possible space bridge connections. _Given the sector arrangements of both space regions, your task is to find the total strength of the two regions. Unfortunately, if the strength isn’t as expected, the Supreme Commander will use his “Force Choke” on you, so good luck!_ **Input** Input starts with an integer **T (, denoting the number of test cases.** Each case starts with a line containing two integers **n** and **m (1 denoting the number of sectors in the two space regions correspondingly. The next **n-1** lines denotes the sector arrangement of the first region. Each line will contain **u** and **v (1

N/A

N/A