Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has a tree $G$ with $N$ nodes (numbered $1$ through $N$) and $N-1$ undirected edges. For each node $u$ in the tree, he can assign directions to the edges in such a way that $u$ is reachable from all the other nodes. Let $C_{u}$ be the number of valid [topological orderings] in the resulting directed acyclic graph.

This way, Chef obtains $N$ pairs $(C_{1},1), (C_{2},2), \ldots, (C_{N},N)$ and he sorts all these pairs $(C_{i}, i)$ in descending order (first by $C_{i}$ and in the case of a tie by $i$).

For example, consider the tree below:

The sorted list of pairs is $((2,2), (1,3), (1,1))$.

Chef quizzes you on this list ― he wants you to find the $K$-th pair in the sorted list. To make that task easier, Chef only asks for $K = 1$ (the largest pair) or $K = 2$ (the second largest pair). Since the number of topological orderings can be very large, compute it modulo $10^{9}+7$.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $K$.
Each of the next $N-1$ lines contains two space-separated integers $u$ and $v$, denoting that nodes $u$ and $v$ are connected by an edge.

------ Output ------
For each test case, print a single line containing two space-separated integers $u$ and $C_{u}$ modulo $10^{9}+7$, where $(C_{u}, u)$ is the $K$-th pair in the sorted list.

------ Constraints ------
$1 ≤ T ≤ 5$
$1 ≤ N ≤ 5 \cdot 10^{5}$
$1 ≤ K ≤ 2$
$1 ≤ u,v ≤ N$
the graph described on the input is a tree
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$

------ Subtasks ------
Subtask #1 (10 points): $N ≤ 10$

Subtask #2 (30 points): $K = 1$

Subtask #3 (60 points): $K = 2$

----- Sample Input 1 ------
1

4 2

1 2

2 3

2 4
----- Sample Output 1 ------
4 2
----- explanation 1 ------
Example case 1: The tree is

• For $u = 1$, there are $C_{1} = 2$ possible topological orderings: $(3,4,2,1)$ and $(4,3,2,1)$
• For $u = 2$, there are $C_{2} = 6$ possible topological orderings: $(3,4,1,2)$, $(4,3,1,2)$, $(3,1,4,2)$, $(4,1,3,2)$, $(1,3,4,2)$ and $(1,4,3,2)$.
• For $u = 3$, there are $C_{3} = 2$ possible topological orderings: $(1,4,2,3)$ and $(4,1,2,3)$.
• For $u = 4$, there are $C_{4} = 2$ possible topological orderings: $(3,1,2,4)$ and $(1,3,2,4)$.

The sorted list of pairs is $((6,2), (2,4), (2,3), (2,1))$. The node for the $2$-nd pair is $4$ and the corresponding number of topological orderings modulo $10^{9}+7$ is $2$.

见题面

见题面