Corruption again

Problem code: IOPC1216

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.

Input

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.

Output

For each test case, print the maximum value of inconvenience factor achievable among all the possible choices of the patrolled road to be blocked.

Example

Input:
1
6 3
0 1
1 2
1 3
3 4
3 5
0 2
0 4
4 5

Output:
2
Author: razimantv
Date Added: 13-01-2012
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: C99 strict, CPP 4.0.0-8, CPP 4.3.2, JAVA, PAS fpc, PAS gpc, PYTH, PYTH 3.1.2


Comments

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions