All submissions for this problem are available.
After the first series of protests disrupted the road traffic in Dystopia, the government decided to take counter measures. It chose a few of the roads as high priority roads and sent military vehicles to patrol them. The roads were chosen in a way that it was possible to move from any junction to any other junction just using the patrolled roads. Also, the number of roads chosen was the minimum possible (N-1, where N is the number of junctions).
After this, people were able to travel without hindrance from the protestors and the protest wasn't taken seriously anymore. Hence the leader of the protest decided to take things to the next level. He decided that he would personally lead the group which blocks one of the patrolled roads - The military would not dare to touch the group then.
Blocking a patrolled road would divide the road network into two parts A and B such that it would be possible to travel between every pair of junctions in A (and every pair of junctions in B) using patrolled roads alone but it would not be possible to move from a junction in A to a junction in B using patrolled roads alone. People then have to take unpatrolled roads with one junction in A and the other in B. The leader terms the number of such inter-part roads as the inconvinence factor for the patrolled road being blocked.
Given the road network, find out the maximum inconvenience factor achievable by choosing the patrolled road to block.
The first line of the input contains T, the number of test cases (T ≤ 5). Following this are the descriptions of the T test cases. The first line of each test case contains two space separated integers N and M - The number of junctions and unpatrolled roads in the network(1 ≤ N ≤ 10000; 0 ≤ M ≤ 30000). Following this are N-1 lines, describing the patrolled roads in the network. Each line will contain two space separated integers i and j, denoting that there is a patrolled road between i and j. This is followed by M lines describing the unpatrolled roads in a similar fashion. You are assured that there is not more than one direct road between any pair of junctions.
For each test case, print the maximum value of inconvenience factor achievable among all the possible choices of the patrolled road to be blocked.
Input: 1 6 3 0 1 1 2 1 3 3 4 3 5 0 2 0 4 4 5 Output: 2
|Time Limit:||0.130625 sec|
|Source Limit:||50000 Bytes|
|Languages:||CPP14, JAVA, PYTH, PYTH 3.6, PAS fpc, PAS gpc, GO, NODEJS, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.