HDU 5300 Angry Trees

内存限制：256 MiB 时间限制：12 Sec

JRY is so rich that he bought too many trees and planted them in his yard. Because of his personal preference, all these trees have the same shape. At first, these trees were small and peaceful, but after growing for several years, they become huge and compete for the limited water and nutrition. Therefore, they become angry, and their common enemy is JRY, because it is JRY who planted them in such a "small" place (although his yard is the biggest in the world).

There are m angry trees, and each angry tree has n nodes and n−1 branches. All the angry trees decide to combine together, and they made extra m−1 branches so that they can be one. Moreover, they select the first node of the first tree to be the root of the whole huge tree. Now, there is a terribly enormous tree with nm nodes and nm−1 branches.

The trees come up with an idea to revenge. When JRY is sleeping, they drag JRY onto one of the nodes, and steal all JRY's money and put it onto one node too (the two nodes can be either same or different). When JRY wakes up, he definitely will go for these money. Every time JRY moves down along a branch (moving towards the root), he will spend 1 unit time, and when he moves up along a branch (moving away from the root), he will spend 2 unit time. Additionally, smart JRY will always move along the shortest path on the tree between him and his money.

One nightmare of the trees is to find the longest time that JRY need to find his money, and they also need to know how many different ways there are to get this longest time (two ways are considered different if and only if JRY's initial position is different or the money's position is different). Can you help them?

The first line of the input is a single integer T, indicating the number of testcases.

For each testcase, the first line is two integers n and m (1n,m50000). Each of the next n−1 lines contains two integers x and y, which represent one branch (x,y) in every tree. Each of the following m−1 lines contains four integers x,a,y,b, which means there is an additional branch connecting the a-th node of the x-th tree and the b-th node of the y-th tree. It is guaranteed that either every small tree or the whole tree is an acyclic connected undirected graph. Please be aware that the first node (the node numbered 1) of the first tree (the tree numbered 1) is the root of the whole tree.

It is guaranteed that for all the testcases, Siga(n)+Sigma(m)<=1000000.

For each testcase, print two space-separated integers indicating the longest time JRY need to find his money and the ways of position to reach this upper bound.

样例输入

样例输出


			11 2

22 3

#4301. HDU 5300 Angry Trees

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示