#4042. [Cerc2014] parades

内存限制:128 MiB 时间限制:10 Sec


In The City of Eternal Festivities, there are n street junctions and n - I bidirectional streets,eac
h street connecting two of the junctions. Between every two junctions, there is exactly one(direct o
r indirect) path connecting them. No junction is an endpoint for more than 10 streets.Every 13th of 
September (the 256th day of the year), there are many festivities going on inThe City. In particular
, the citizens want to organize m parades. The parade number 7; starts atjunction ui and ends at vi,
 following the unique path between the endpoints.As the mayor of The City, you are responsible for c
itizens' safety. Therefore you decreed thatno two parades are ever allowed to use the same street, t
hough they can have common junctions,or even common endpoints.To appease your citizens, try to organ
ize as many parades as possible, without breaking thesafety regulations.


The first line of input contains the number of test cases T. The descriptions of the test cases 
The first line of each test case contains a single integer: the number of junctions n (2《 n≤1000).
 Each of the next n - I lines contains two integers a, b (1《 a≠ b≤ n), denoting thatjunctions a a
nd b are connected by a street. Each junction has at most 10 streets leaving it.The next line contai
ns a single integer: the number of planned parades m, 0≤ m <(彩.Each of the next m lines contains t
wo integers ui, vi (1≤ ui≠ vi≤n), meaning that a parade isplanned to start at junction ui, and fi
nish at junction vi. No two parades share both endpoints.


For each test case, output one line containing the largest number of parades that can beorganized wi
th no street used bv more than one parade.



1 2
2 3
3 4
3 5
3 6
1 3
4 5
5 6
6 4