8042: BZOJ4042：[Cerc2014] parades

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. 一个树，d(v)<=10，给定m条path，找出最多不共边的path，不需要方案。  n<=1000,m<=总路径数

输入格式

The first line of input contains the number of test cases T. The descriptions of the test cases  follow:  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
6
1 2
2 3
3 4
3 5
3 6
4
1 3
4 5
5 6
6 4

样例输出

2

提示

没有写明提示

题目来源

没有写明来源