Angry Trees

Time Limit: 6000 ms Memory Limit: 262144 KiB

Problem Description

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 n1 branches. All the angry trees decide to combine together, and they made extra m1 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 nm1 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?

Input

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 (1n,m50000). Each of the next n1 lines contains two integers x and y, which represent one branch (x,y) in every tree. Each of the following m1 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, n+m1000000.

Output

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.

Sample Input

2
3 3
3 1
2 1
3 1 2 2
1 3 2 1
3 8
3 1
2 3
4 3 3 1
3 1 2 3
6 2 1 3
8 3 7 3
5 3 7 3
6 3 7 2
8 3 2 2

Sample Output

11 2
22 3

Hint

Please be careful about the problem named STACK_OVERFLOW

Source

2015 Multi-University Training Contest 2