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$.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms

Greedy algorithms

Tree algorithms

Dynamic programming

Data structures


Solutions:
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
lis = lambda : list(input().strip().split())
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline().strip()
stdint = lambda : int(stdin.readline())
stdmul = lambda : map(int, stdin.readline().strip().split())
stdseq = lambda : list(map(int, stdin.readline().strip().split()))
stdlis = lambda : list(stdin.readline().strip().split())
stdpr = lambda x: stdout.write(str(x))
mod = 10 ** 9 + 7

class Graph:

	def __init__(self, edges, N):
		self.adjList = [[] for _ in range(N)]
		self.indegree = [0] * N
		for (src, dest) in edges:
			self.adjList[src].append(dest)
			self.indegree[dest] = self.indegree[dest] + 1

def findAllTopologicalOrders(graph, path, discovered, N, cnt):
	for v in range(N):
		if graph.indegree[v] == 0 and (not discovered[v]):
			for u in graph.adjList[v]:
				graph.indegree[u] = graph.indegree[u] - 1
			path.append(v)
			discovered[v] = True
			findAllTopologicalOrders(graph, path, discovered, N, cnt)
			for u in graph.adjList[v]:
				graph.indegree[u] = graph.indegree[u] + 1
			path.pop()
			discovered[v] = False
	if len(path) == N:
		cnt[0] += 1

def printAllTopologicalOrders(graph, cnt):
	N = len(graph.adjList)
	discovered = [False] * N
	path = []
	findAllTopologicalOrders(graph, path, discovered, N, cnt)

def dfs(graph, visited, i, edges):
	visited[i] = True
	for j in graph[i]:
		if not visited[j]:
			edges.append(tuple([j, i]))
			dfs(graph, visited, j, edges)
N = 5 * 10 ** 5 + 5
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1, 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans

def dfs2(graph, temp, subtree, visited, i):
	visited[i] = True
	(ans, s) = (1, 0)
	for j in graph[i]:
		if not visited[j]:
			current = dfs2(graph, temp, subtree, visited, j)
			s += current
			ans = ans * Binomial(s, current, mod)
			ans = ans % mod
			ans = ans * temp[j]
			ans = ans % mod
	ans %= mod
	temp[i] = ans
	return s + 1

def getNode(graph, temp, subtree, visited, i, AA):
	visited[i] = True
	s = 0
	curr = 0
	for x in graph[i]:
		if not visited[x]:
			curr = getNode(graph, temp, subtree, visited, x, AA)
			s += curr
			nn = min(len(graph) - curr, curr)
			AA.append([nn, [x, i]])
	subtree[i] = s + 1
	return s + 1
factorial(mod)
InverseofNumber(mod)
InverseofFactorial(mod)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	graph = dict()
	for i in range(n):
		graph[i] = []
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		graph[u].append(v)
		graph[v].append(u)
	if n == 1:
		(k1, k2) = (0, 0)
		if k == 1:
			visited = [False] * n
			temp = [0] * n
			subtree = [0] * n
			dfs2(graph, temp, subtree, visited, k1)
			print(k1, temp[k1] % mod)
		else:
			visited = [False] * n
			temp = [0] * n
			subtree = [0] * n
			dfs2(graph, temp, subtree, visited, k2)
			print(k2, temp[k2] % mod)
		continue
	aa = []
	subtree = [0] * n
	visited = [False] * n
	temp = [0] * n
	getNode(graph, temp, subtree, visited, 0, aa)
	idx = 1
	aa.sort(reverse=True)
	(k1, k2) = (0, 0)
	if aa[0][0] != aa[1][0]:
		(x, y) = (aa[0][1][0], aa[0][1][1])
		if subtree[x] == n - subtree[x]:
			k1 = max(x, y)
			k2 = min(x, y)
		elif subtree[x] > n - subtree[x]:
			k1 = x
			k2 = y
		else:
			k2 = x
			k1 = y
	else:
		t = []
		if aa[0][1][0] == aa[1][1][0] or aa[0][1][0] == aa[1][1][1]:
			k1 = aa[0][1][0]
		else:
			k1 = aa[0][1][1]
		idx = 1
		t.append(aa[0][1][0]) if aa[0][1][0] != k1 else t.append(aa[0][1][1])
		nn = len(aa)
		while idx < nn and aa[idx - 1][0] == aa[idx][0]:
			t.append(aa[idx][1][0]) if aa[idx][1][0] != k1 else t.append(aa[idx][1][1])
			idx += 1
		k2 = max(t)
	if k == 1:
		visited = [False] * n
		temp = [0] * n
		dfs2(graph, temp, subtree, visited, k1)
		print(k1 + 1, temp[k1] % mod)
	else:
		visited = [False] * n
		temp = [0] * n
		dfs2(graph, temp, subtree, visited, k2)
		print(k2 + 1, temp[k2] % mod)


from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7

def dfscent(adj, v, par, n, centroid, sz):
	sz[v] = 1
	iscentroid = True
	for a in adj[v]:
		if a != par:
			dfscent(adj, a, v, n, centroid, sz)
			sz[v] += sz[a]
			if sz[a] > n / 2:
				iscentroid = False
	if n - sz[v] > n / 2:
		iscentroid = False
	if iscentroid:
		centroid.append(v)

def findCentroid(adj, n, sz):
	centroid = []
	dfscent(adj, 0, -1, n, centroid, sz)
	return max(centroid)

def topoval(adj, v, par, dp, sz):
	dp[v] = 1
	sz[v] = 1
	for a in adj[v]:
		if a != par:
			topoval(adj, a, v, dp, sz)
			dp[v] = dp[v] * dp[a] % MOD
			dp[v] = dp[v] * invfact[sz[a]] % MOD
			sz[v] += sz[a]
	dp[v] = dp[v] * fact[sz[v] - 1] % MOD
	return dp[v] % MOD
fact = [1] * (5 * 10 ** 5 + 10)
invfact = [1] * (5 * 10 ** 5 + 10)
for i in range(1, len(fact)):
	fact[i] = fact[i - 1] * i % MOD
	invfact[i] = pow(fact[i], MOD - 2, MOD)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	adj = [[] for _ in range(int(n))]
	for _ in range(int(n - 1)):
		(u, v) = map(int, input().split())
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	sz = [0] * n
	first = findCentroid(adj, n, sz)
	dp = [-1] * n
	firstans = topoval(adj, first, -1, dp, sz)
	if k == 1:
		print(first + 1, firstans)
	else:
		second = adj[first][0]
		for v in adj[first]:
			if sz[v] > sz[second]:
				second = v
			if sz[v] == sz[second] and v > second:
				second = v
		secondans = topoval(adj, second, -1, dp, sz)
		print(second + 1, secondans)


from collections import deque
p = 10 ** 9 + 7
facts = [1] * (5 * 10 ** 5 + 10)
invfacts = [1] * (5 * 10 ** 5 + 10)
for i in range(1, len(facts)):
	facts[i] = facts[i - 1] * i % p
	invfacts[i] = pow(facts[i], p - 2, p)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	graph = [[] for i in range(n)]
	edges = [0 for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		graph[u].append(v)
		graph[v].append(u)
		edges[u] += 1
		edges[v] += 1
	edges[0] += 2
	par = [-1 for i in range(n)]
	que = deque([0])
	while que:
		i = que.popleft()
		for j in graph[i]:
			if j != par[i]:
				par[j] = i
				que.append(j)
	count = [1 for i in range(n)]
	d = [1 for i in range(n)]
	que = deque([])
	for i in range(n):
		if edges[i] == 1:
			que.append(i)
	while que:
		i = que.popleft()
		d[i] = d[i] * facts[count[i] - 1] % p
		edges[par[i]] -= 1
		count[par[i]] += count[i]
		d[par[i]] = d[par[i]] * invfacts[count[i]] % p * d[i] % p
		if edges[par[i]] == 1:
			que.append(par[i])
	d[0] = d[0] * facts[count[0] - 1] % p
	res = []
	anst = [0 for i in range(n)]
	anst[0] = d[0]
	res.append([1, 0])
	ans = [0 for i in range(n)]
	ans[0] = 1
	que = deque([(0, -1)])
	while que:
		(i, parent) = que.popleft()
		for j in graph[i]:
			if j != parent:
				c = count[j]
				ans[j] = ans[i] * c / (n - c)
				anst[j] = int(anst[i] * c * pow(n - c, p - 2, p)) % p
				res.append([ans[j], j])
				que.append((j, i))
	res.sort(key=lambda x: (x[0], x[1]), reverse=True)
	print(res[k - 1][1] + 1, anst[res[k - 1][1]])


from collections import deque
p = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	facts = [1] * (n + 2)
	invfacts = [1] * (n + 2)
	for i in range(1, len(facts)):
		facts[i] = facts[i - 1] * i % p
		invfacts[i] = pow(facts[i], p - 2, p)
	curr_edges = [0] * (n + 1)
	adj = [[] for i in range(n + 1)]
	const = [1] * (n + 1)
	final = [0] * (n + 1)
	for i in range(n - 1):
		(u, v) = list(map(int, input().split()))
		adj[u].append(v)
		adj[v].append(u)
		curr_edges[u] += 1
		curr_edges[v] += 1
	highest = 1
	curr_edges[highest] += 1
	par = [0] * (n + 1)
	total = [1] * (n + 1)
	count = [1] * (n + 1)
	q = deque([highest])
	while len(q):
		s = q.popleft()
		for child in adj[s]:
			if child != par[s]:
				par[child] = s
				q.append(child)
	leaves = []
	for i in range(1, n + 1):
		if curr_edges[i] == 1:
			leaves.append(i)
	curr = deque(leaves)
	while curr:
		i = curr.popleft()
		total[i] = total[i] * facts[count[i] - 1] % p
		count[par[i]] += count[i]
		total[par[i]] = total[par[i]] * total[i] % p * invfacts[count[i]] % p
		curr_edges[par[i]] -= 1
		if curr_edges[par[i]] == 1:
			curr.append(par[i])
	final[highest] = total[highest]
	curr = [highest]
	ans = 1
	while len(curr):
		s = curr.pop()
		for child in adj[s]:
			if child != par[s]:
				final[child] = final[s] * count[child] % p * pow(n - count[child], p - 2, p) % p
				const[child] = const[s] * count[child] / (n - count[child])
				curr.append(child)
	pair = [(const[i], i) for i in range(1, n + 1)]
	pair.sort(reverse=True)
	ind = pair[k - 1][1]
	print(str(ind) + ' ' + str(final[ind]))


import sys
sys.setrecursionlimit(10 ** 6)
mo = 1000000007
max_size = 1000000
facinv = [0] * max_size
f = [0] * max_size
modinv = [0] * max_size
f[0] = 1
facinv[0] = facinv[1] = modinv[0] = modinv[1] = 1
for i in range(1, max_size):
	f[i] = f[i - 1] * i % mo
for i in range(2, max_size):
	facinv[i] = facinv[mo % i] * (mo - mo // i) % mo
for i in range(2, max_size):
	modinv[i] = modinv[i - 1] * facinv[i] % mo

def nCr(n, r):
	if r == n:
		return 1
	if n < r:
		return 0
	ans = f[n] * modinv[r] % mo
	ans = ans * modinv[n - r] % mo
	return ans

def get_pre(node, arr, sub_arr, visited, arr1):
	visited[node] = 1
	temp_s = 0
	for neigh in arr[node]:
		if visited[neigh] == 0:
			get_pre(neigh, arr, sub_arr, visited, arr1)
			x = sub_arr[neigh]
			arr1.append([min(x, n - x), [neigh, node]])
			temp_s += x
	sub_arr[node] = temp_s + 1

def sub_tree_calc(arr, visited, node, sub_arr):
	visited[node] = 1
	temp_s = 0
	for i in range(len(arr[node])):
		if visited[arr[node][i]] == 0:
			sub_tree_calc(arr, visited, arr[node][i], sub_arr)
			temp_s += sub_arr[arr[node][i]]
	sub_arr[node] = temp_s + 1

def get_comb(a):
	if len(a) == 0:
		return 1
	temp_s = a[0]
	p = 1
	for i in range(1, len(a)):
		temp_s += a[i]
		t = nCr(temp_s, a[i])
		p = p * t % mo
	return p

def dfs(arr, visited, node, sub_arr, dp):
	visited[node] = 1
	temp_s = []
	p = 1
	for i in range(len(arr[node])):
		if visited[arr[node][i]] == 0:
			arr1 = dfs(arr, visited, arr[node][i], sub_arr, dp)
			p = p * arr1 % mo
			temp_s.append(sub_arr[arr[node][i]])
	dp[node] = p * get_comb(temp_s) % mo
	return dp[node]

def modinvfn(n):
	arr1 = mo
	x = 0
	temp_s = 1
	if arr1 == 1:
		return 0
	while n > 1:
		p = n // arr1
		t = arr1
		arr1 = n % arr1
		n = t
		t = x
		x = temp_s - p * x
		temp_s = t
	if temp_s < 0:
		temp_s += mo
	return temp_s

def traverse(node, arr, visited, sub_arr, dp, k, n):
	visited[node] = 1
	temp_s = []
	p = 1
	for i in range(len(arr[node])):
		if visited[arr[node][i]] == 0:
			arr1 = dp[arr[node][i]]
			p = p * arr1 % mo
			temp_s.append(sub_arr[arr[node][i]])
	if k != -1:
		x = dp[k]
		x = x * modinvfn(dp[node]) % mo
		x = x * modinvfn(nCr(n - 1, sub_arr[node])) % mo
		p = p * x % mo
		temp_s.append(n - sub_arr[node])
	dp[node] = p * get_comb(temp_s) % mo
	for i in range(len(arr[node])):
		if visited[arr[node][i]] == 0:
			traverse(arr[node][i], arr, visited, sub_arr, dp, node, n)

def calc(arr, n, sub_arr, dp, node):
	visited = [0] * n
	sub_tree_calc(arr, visited, node, sub_arr)
	for i in range(n):
		visited[i] = 0
	dfs(arr, visited, node, sub_arr, dp)

def compute(dp, arr, node, visited):
	visited[node] = 1
	p = 1
	temp_s = 0
	for neigh in arr[node]:
		if visited[neigh] == 0:
			x = compute(dp, arr, neigh, visited)
			temp_s += x
			t1 = nCr(temp_s, x)
			t2 = dp[neigh]
			p = p * t1 * t2 % mo
	dp[node] = p
	return temp_s + 1
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [[] for i in range(n)]
	dp = [0] * n
	visited = [False] * n
	arr1 = []
	sub_arr = [None] * n
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		arr[u - 1].append(v - 1)
		arr[v - 1].append(u - 1)
	if n <= 10:
		temp_s = []
		calc(arr, n, sub_arr, dp, 0)
		traverse(0, arr, visited, sub_arr, dp, -1, n)
		for i in range(n):
			temp_s.append((int(dp[i]), int(i + 1)))
		temp_s.sort(reverse=True)
		print(str(temp_s[k - 1][1]) + ' ' + str(temp_s[k - 1][0]))
	else:
		get_pre(0, arr, sub_arr, visited, arr1)
		cur_pos = 1
		while len(arr1) < n + 1:
			arr1.append([0, [-1, -1]])
		arr1.sort(key=lambda x: x[0], reverse=True)
		if arr1[0][0] != arr1[1][0]:
			x = arr1[0][1][0]
			y = arr1[0][1][1]
			if sub_arr[x] != n - sub_arr[x]:
				if sub_arr[x] > n - sub_arr[x]:
					k1 = x
					k2 = y
				else:
					k1 = y
					k2 = x
			else:
				k1 = max(x, y)
				k2 = min(x, y)
		else:
			a = []
			if not (arr1[0][1][0] == arr1[1][1][0] or arr1[0][1][0] == arr1[1][1][1]):
				k1 = arr1[0][1][1]
				a.append(arr1[0][1][0])
			else:
				k1 = arr1[0][1][0]
				a.append(arr1[0][1][1])
			cur_pos = 1
			while cur_pos < n and arr1[cur_pos - 1][0] == arr1[cur_pos][0]:
				if arr1[0][1][1] != k1:
					a.append(arr1[cur_pos][1][1])
				else:
					a.append(arr1[cur_pos][1][0])
				cur_pos = cur_pos + 1
			k2 = max(a)
		visited = [0] * n
		dp = [0] * n
		if k == 2:
			compute(dp, arr, k2, visited)
			node = k2 + 1
			combb = dp[k2] % mo
			combb = (combb + mo) % mo
		else:
			node = k1 + 1
			compute(dp, arr, k1, visited)
			combb = dp[k1] % mo
			combb = (combb + mo) % mo
		print(node, combb)


from itertools import permutations as perm
from fractions import Fraction
from collections import *
from sys import stdin
from bisect import *
from heapq import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
N = int(500000.0) + 1
fac = [1] * N
for i in range(2, N):
	fac[i] *= fac[i - 1] * i
	fac[i] %= mod
(t,) = gil()

def cal(root, adj, n):
	dp = [0] * (n + 1)
	ans = fac[n]
	dp[0] = 1
	stack = [root]
	vis = [0] * (n + 1)
	while stack:
		p = stack[-1]
		if vis[p]:
			dp[p] = 1
			for c in adj[p]:
				dp[p] += dp[c]
			ans *= pow(dp[p], mod - 2, mod)
			ans %= mod
			stack.pop()
		else:
			vis[p] = 1
			for c in adj[p]:
				if not vis[c]:
					stack.append(c)
	return ans

def getCenters(adj, n):
	dp = [0] * (n + 1)
	stack = [1]
	vis = [0] * (n + 1)
	while stack:
		p = stack[-1]
		if vis[p]:
			stack.pop()
			for c in adj[p]:
				dp[p] += dp[c]
			dp[p] += 1
		else:
			vis[p] = 1
			for c in adj[p]:
				if not vis[c]:
					stack.append(c)
	p = 1
	lmt = n // 2
	while 1:
		np = max(adj[p], key=lambda x: dp[x])
		if dp[np] <= lmt:
			break
		dp[p] -= dp[np]
		p = np
		dp[p] = n
	return (p, dp)
for _ in range(t):
	(n, k) = gil()
	if n == 1:
		print(1, 1)
		continue
	adj = [[] for _ in range(n + 1)]
	adj_ = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(x, y) = gil()
		adj[x].append(y)
		adj[y].append(x)
		adj_[x].append(y)
		adj_[y].append(x)
	if n < 11:
		if k == 1:
			ci = getCenters(adj_, n)
			print(ci, cal(ci, adj, n))
		else:
			ans = []
			for i in range(1, n + 1):
				ans.append((cal(i, adj, n), i))
			ans.sort(reverse=True)
			(val, node) = ans[k - 1]
			val %= mod
			print(node, val)
	elif k == 1:
		(ci, _) = getCenters(adj_, n)
		print(ci, cal(ci, adj, n))
	else:
		(ci, dp) = getCenters(adj_, n)
		ans = []
		for c in adj[ci]:
			cv = dp[c] / (n - dp[c])
			ans.append((cv, c))
		(_, node) = max(ans)
		print(node, cal(node, adj, n))


import sys
sys.setrecursionlimit(10 ** 6)
z = int(1000000000.0) + 7
size = int(1000000.0)
invf = [0] * size
f = [0] * size
modi = [0] * size
f[0] = 1
invf[0] = 1
invf[1] = 1
modi[0] = 1
modi[1] = 1
for i in range(1, size):
	f[i] = f[i - 1] * i % z
for i in range(2, size):
	invf[i] = invf[z % i] * (z - z // i) % z
for i in range(2, size):
	modi[i] = modi[i - 1] * invf[i] % z

def mi(n):
	m = z
	x = 0
	s = 1
	if m == 1:
		return 0
	while n > 1:
		p = n // m
		t = m
		m = n % m
		n = t
		t = x
		x = s - p * x
		s = t
	if s < 0:
		s += z
	return s

def C(n, r):
	if r == n:
		return 1
	if n < r:
		return 0
	ans = f[n] * modi[r] % z
	ans = ans * modi[n - r] % z
	return ans

def compute(a):
	if len(a) == 0:
		return 1
	s = a[0]
	p = 1
	for i in range(1, len(a)):
		s += a[i]
		t = C(s, a[i])
		p = p * t % z
	return p

def calculate(node, e, d, v, m):
	v[node] = 1
	s = 0
	for child in e[node]:
		if v[child] == 0:
			calculate(child, e, d, v, m)
			x = d[child]
			m.append([min(x, n - x), [child, node]])
			s += x
	d[node] = s + 1

def solve(node, v, dp, e):
	v[node] = 1
	p = 1
	s = 0
	for child in e[node]:
		if v[child] == 0:
			x = solve(child, v, dp, e)
			s += x
			t1 = C(s, x)
			t2 = dp[child]
			p = p * t1 * t2 % z
	dp[node] = p
	return s + 1

def topo(m):
	m.sort(key=lambda x: x[0], reverse=True)
	return m

def find(node, e, v, d):
	v[node] = 1
	s = 0
	for i in range(len(e[node])):
		if v[e[node][i]] == 0:
			find(e[node][i], e, v, d)
			s += d[e[node][i]]
	d[node] = s + 1

def dfs(node, e, v, d, dp):
	v[node] = 1
	s = []
	p = 1
	for i in range(len(e[node])):
		if v[e[node][i]] == 0:
			m = dfs(e[node][i], e, v, d, dp)
			p = p * m % z
			s.append(d[e[node][i]])
	dp[node] = p * compute(s) % z
	return dp[node]

def code(node, e, v, d, dp, k, n):
	v[node] = 1
	s = []
	p = 1
	for i in range(len(e[node])):
		if v[e[node][i]] == 0:
			m = dp[e[node][i]]
			p = p * m % z
			s.append(d[e[node][i]])
	if k != -1:
		x = dp[k]
		x = x * mi(dp[node]) % z
		x = x * mi(C(n - 1, d[node])) % z
		p = p * x % z
		s.append(n - d[node])
	dp[node] = p * compute(s) % z
	for i in range(len(e[node])):
		if v[e[node][i]] == 0:
			code(e[node][i], e, v, d, dp, node, n)

def preprocess(node, e, n, d, dp):
	v = [0] * n
	find(node, e, v, d)
	for i in range(n):
		v[i] = 0
	dfs(node, e, v, d, dp)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n > 10:
		tree = {}
		m = []
		d = [0] * (n + 1)
		vis = [0] * (n + 1)
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			u = u - 1
			v = v - 1
			if v in tree:
				tree[v].append(u)
			else:
				tree[v] = [u]
			if u in tree:
				tree[u].append(v)
			else:
				tree[u] = [v]
		calculate(0, tree, d, vis, m)
		pos = 1
		m = topo(m)
		while len(m) < n + 1:
			m.append([0, [-1, -1]])
		if m[0][0] != m[1][0]:
			x = m[0][1][0]
			y = m[0][1][1]
			if d[x] != n - d[x]:
				if d[x] > n - d[x]:
					k1 = x
					k2 = y
				else:
					k1 = y
					k2 = x
			else:
				k1 = max(x, y)
				k2 = min(x, y)
		else:
			a = []
			if not (m[0][1][0] == m[1][1][0] or m[0][1][0] == m[1][1][1]):
				k1 = m[0][1][1]
				a.append(m[0][1][0])
			else:
				k1 = m[0][1][0]
				a.append(m[0][1][1])
			pos = 1
			while pos < n and m[pos - 1][0] == m[pos][0]:
				if m[0][1][1] != k1:
					a.append(m[pos][1][1])
				else:
					a.append(m[pos][1][0])
				pos = pos + 1
			k2 = max(a)
		vis = [0] * n
		dp = [0] * n
		if k == 2:
			solve(k2, vis, dp, tree)
			node = k2 + 1
			res = (dp[k2] % z + z) % z
		else:
			node = k1 + 1
			solve(k1, vis, dp, tree)
			res = (dp[k1] % z + z) % z
		print(node, res)
	else:
		vis = [0] * n
		d = [0] * n
		dp = [0] * n
		e = [[] for i in range(n)]
		s = []
		for i in range(n - 1):
			(u, v) = map(int, input().split())
			e[u - 1].append(v - 1)
			e[v - 1].append(u - 1)
		preprocess(0, e, n, d, dp)
		code(0, e, vis, d, dp, -1, n)
		for i in range(n):
			s.append((int(dp[i]), int(i + 1)))
		s.sort(reverse=True)
		print(str(s[k - 1][1]) + ' ' + str(s[k - 1][0]))


N = 500005
mod = 10 ** 9 + 7
(fact, invf, invnum) = ([0] * N, [0] * N, [0] * N)
(fact[0], fact[1], invf[0], invf[1]) = (1, 1, 1, 1)
invnum[0] = invnum[1] = 1
for i in range(2, N):
	invnum[i] = invnum[mod % i] * (mod - mod // i) % mod
	fact[i] = fact[i - 1] * i % mod
	invf[i] = invnum[i] * invf[i - 1] % mod

def dfs(node):
	v[node] = 1
	(ans, sub) = (1, 0)
	for x in adj[node]:
		if v[x] == 0:
			c = dfs(x)
			sub += c
			if c > sub:
				ans = 0
			else:
				ans = ans * (fact[sub] * invf[c] % mod * invf[sub - c]) % mod
			ans = ans * count[x] % mod
	count[node] = ans
	return sub + 1

def create(node):
	v[node] = 1
	sub = 0
	for x in adj[node]:
		if v[x] == 0:
			curr = create(x)
			sub += curr
			mini = min(curr, n - curr)
			seq.append([mini, [x, node]])
	sub += 1
	sub_tree[node] = sub
	return sub
import sys
t = int(input())
for test in range(t):
	(n, k) = map(int, input().split())
	if n <= 10 ** 5 + 100:
		sys.setrecursionlimit(100004)
	else:
		sys.setrecursionlimit(500005)
	adj = []
	for i in range(n):
		adj.append([])
	v = [0] * n
	sub_tree = [0] * n
	count = [0] * n
	seq = []
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		adj[a - 1].append(b - 1)
		adj[b - 1].append(a - 1)
	if n == 1:
		print(1, 1)
	elif n == 2:
		if k == 1:
			print(2, 1)
		else:
			print(1, 1)
	else:
		create(0)
		idx = 1
		(seq.sort(), seq.reverse())
		if seq[0][0] != seq[1][0]:
			x = seq[0][1][0]
			y = seq[0][1][1]
			if sub_tree[x] == n - sub_tree[x]:
				k1 = max(x, y)
				k2 = min(x, y)
			elif sub_tree[x] > n - sub_tree[x]:
				k1 = x
				k2 = y
			else:
				k2 = x
				k1 = y
		else:
			stack = []
			if seq[0][1][0] == seq[1][1][0] or seq[0][1][0] == seq[1][1][1]:
				k1 = seq[0][1][0]
			else:
				k1 = seq[0][1][1]
			i = 1
			if seq[0][1][0] != k1:
				stack.append(seq[0][1][0])
			else:
				stack.append(seq[0][1][1])
			while i != n and i < len(seq) and (seq[i - 1][0] == seq[i][0]):
				if seq[i][1][0] != k1:
					stack.append(seq[i][1][0])
				else:
					stack.append(seq[i][1][1])
				i += 1
			k2 = max(stack)
		v = [0] * n
		count = [0] * n
		if k == 1:
			dfs(k1)
			print(k1 + 1, count[k1] % mod)
		else:
			dfs(k2)
			print(k2 + 1, count[k2] % mod)


import sys

def arrIn():
	return list(map(int, input().split()))

def mapIn():
	return map(int, input().split())
mod = 10 ** 9 + 7
fact = [0] * 500005
fact[0] = 1
inv_fact = [0] * 500005
(inv_fact[0], inv_fact[1]) = (1, 1)
endb = 500005
invn = [0] * endb
invn[0] = invn[1] = 1
for i in range(2, endb):
	invn[i] = invn[mod % i] * (mod - mod // i) % mod
for i in range(1, endb):
	fact[i] = fact[i - 1] * i % mod
for i in range(2, endb):
	inv_fact[i] = invn[i] * inv_fact[i - 1] % mod

def bincoff(n, r, p):
	if r > n:
		return 0
	if r == n:
		return 1
	return fact[n] * inv_fact[r] % p * inv_fact[n - r] % p

def dfs(node):
	vis[node] = 1
	(ans, subt) = (1, 0)
	for x in adj[node]:
		if vis[x] == 0:
			nw = dfs(x)
			subt += nw
			ans *= bincoff(subt, nw, mod)
			ans %= mod
			ans *= temp[x]
			ans %= mod
	temp[node] = ans % mod
	return subt + 1

def get(node):
	vis[node] = 1
	subt = 0
	for x in adj[node]:
		if vis[x] == 0:
			curr = get(x)
			subt += curr
			mini = min(curr, n - curr)
			aa.append([mini, [x, node]])
	subt += 1
	sub_tree[node] = subt
	return subt
for ii in range(int(input())):
	(n, k) = mapIn()
	if n < 10 ** 5 + 5:
		sys.setrecursionlimit(100004)
	else:
		sys.setrecursionlimit(500005)
	adj = []
	for i in range(n):
		adj.append([])
	vis = [0] * n
	sub_tree = [0] * n
	temp = [0] * n
	aa = []
	for i in range(n - 1):
		(x, y) = mapIn()
		(x, y) = (x - 1, y - 1)
		adj[x].append(y)
		adj[y].append(x)
	if n == 1:
		print(1, 1)
		continue
	get(0)
	idx = 1
	aa.sort()
	aa.reverse()
	if aa[0][0] != aa[1][0]:
		x = aa[0][1][0]
		y = aa[0][1][1]
		if sub_tree[x] == n - sub_tree[x]:
			k1 = max(x, y)
			k2 = min(x, y)
		elif sub_tree[x] > n - sub_tree[x]:
			k1 = x
			k2 = y
		else:
			k2 = x
			k1 = y
	else:
		stack = []
		if aa[0][1][0] == aa[1][1][0] or aa[0][1][0] == aa[1][1][1]:
			k1 = aa[0][1][0]
		else:
			k1 = aa[0][1][1]
		idx = 1
		if aa[0][1][0] != k1:
			stack.append(aa[0][1][0])
		else:
			stack.append(aa[0][1][1])
		g = len(aa)
		while idx != n and idx < g and (aa[idx - 1][0] == aa[idx][0]):
			if aa[idx][1][0] != k1:
				stack.append(aa[idx][1][0])
			else:
				stack.append(aa[idx][1][1])
			idx += 1
		k2 = max(stack)
	vis = [0] * n
	temp = [0] * n
	if k == 1:
		dfs(k1)
		print(k1 + 1, temp[k1] % mod)
	else:
		dfs(k2)
		print(k2 + 1, temp[k2] % mod)


import sys
import math
sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7

def subTreeSizes(el, root, visited, sizes):
	if not visited[root]:
		visited[root] = True
		size = 1
		for u in el[root]:
			subTreeSizes(el, u, visited, sizes)
			size += sizes[u]
		sizes[root] = size
	return sizes

def countOrderings(sizes):
	result = 1
	for i in range(2, len(sizes) + 1):
		result *= i
		result %= MOD
	den = 1
	for size in sizes:
		den *= size
		den %= MOD
	result *= pow(den, MOD - 2, MOD)
	return result % MOD

def subTreeProds(el, visited, sizes, products, root=0, parent=0):
	if not visited[root]:
		visited[root] = True
		if root == 0:
			products[0] = 0
			for size in sizes:
				products[0] += math.log(size)
			for u in el[root]:
				subTreeProds(el, visited, sizes, products, u, root)
		else:
			old_size_parent = sizes[parent]
			old_size_root = sizes[root]
			sizes[root] = old_size_parent
			sizes[parent] = old_size_parent - old_size_root
			products[root] = products[parent] - math.log(old_size_root) + math.log(sizes[parent])
			for u in el[root]:
				subTreeProds(el, visited, sizes, products, u, root)
			sizes[parent] = old_size_parent
			sizes[root] = old_size_root

def solve(el, K):
	sizes = subTreeSizes(el, 0, [False] * len(el), [0] * len(el))
	products = [0] * len(el)
	subTreeProds(el, [False] * len(el), sizes, products)
	pairlist = []
	for index in range(len(products)):
		pairlist.append((products[index], -index))
	pairlist.sort()
	root = -pairlist[K - 1][1]
	sizes = subTreeSizes(el, root, [False] * len(el), [0] * len(el))
	return (root + 1, countOrderings(sizes))
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	el = [[] for _ in range(N)]
	for _ in range(N - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		el[u].append(v)
		el[v].append(u)
	print(*solve(el, K))


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
MAX = 5 * 10 ** 5 + 13
fct = [0] * MAX
fct[0] = 1
for i in range(1, MAX):
	fct[i] = fct[i - 1] * i % MOD

def inv(a):
	return pow(a, MOD - 2, MOD)

def count(u, p=-1):
	s = 1
	for v in g[u]:
		if v != p:
			c = count(v, u)
			s += c
	x[u] = s
	return s

def solve(u, r, p=-1):
	if p == -1:
		for v in g[u]:
			solve(v, r, u)
	else:
		r -= 2 * x[u] - 1
		r += x[p] - 1
		(c1, c2) = (x[u], x[p])
		(x[u], x[p]) = (x[p], x[p] - x[u])
		mini[u - 1] = (-r, u)
		for v in g[u]:
			if v != p:
				solve(v, r, u)
		(x[u], x[p]) = (c1, c2)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	g = [[] for _ in range(n + 5)]
	for _ in range(1, n):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	u = 1
	x = [-1] * (n + 1)
	count(u)
	b = sum(x) - len(x)
	mini = [()] * n
	mini[0] = (-b, 1)
	solve(1, b)
	mini.sort()
	count(mini[-k][1])
	f = fct[n - 1]
	for i in x[1:]:
		if i != n:
			f = f * inv(i) % MOD
	print(mini[-k][1], f)


import sys
sys.setrecursionlimit(10 ** 8)
MOD = 10 ** 9 + 7
DEBUG = False

def debug(*args):
	if DEBUG:
		print(*args)

def populateSubtreeNodeCounts(adjNodes, n, subtreeNodeCounts, nodeIndex, visitedNodes):
	subtreeNodeCount = 1
	visitedNodes[nodeIndex] = True
	for nIndex in adjNodes[nodeIndex]:
		if not visitedNodes[nIndex]:
			subtreeNodeCount += populateSubtreeNodeCounts(adjNodes, n, subtreeNodeCounts, nIndex, visitedNodes)
	subtreeNodeCounts[nodeIndex] = subtreeNodeCount
	return subtreeNodeCount

def findKthMinSubtreeNodeCountsProduct(adjNodes, n, k, subtreeNodeCounts, nodeIndex, visitedNodes, subtreeNodeCountsProduct, prevIndex):
	subtreeNodeCountsProductUpdateVals = []
	for nIndex in adjNodes[nodeIndex]:
		if not visitedNodes[nIndex]:
			subtreeNodeCountsProductUpdateVals.append(((n - subtreeNodeCounts[nIndex]) / subtreeNodeCounts[nIndex], nIndex))
	subtreeNodeCountsProductUpdateVals = sorted(subtreeNodeCountsProductUpdateVals, key=lambda item: (item[0], -1 * item[1]))
	debug(nodeIndex, prevIndex, subtreeNodeCountsProduct, subtreeNodeCountsProductUpdateVals)
	if subtreeNodeCountsProductUpdateVals[0][0] > 1:
		if k == 1:
			return (nodeIndex, subtreeNodeCountsProduct)
		if nodeIndex > 1 and (subtreeNodeCounts[nodeIndex] / (n - subtreeNodeCounts[nodeIndex]) < subtreeNodeCountsProductUpdateVals[0][0] or (subtreeNodeCounts[nodeIndex] / (n - subtreeNodeCounts[nodeIndex]) == subtreeNodeCountsProductUpdateVals[0][0] and prevIndex > subtreeNodeCountsProductUpdateVals[0][1])):
			kthMinProductIndex = prevIndex
			kthMinProduct = subtreeNodeCountsProduct * subtreeNodeCounts[nodeIndex] * pow(n - subtreeNodeCounts[nodeIndex], MOD - 2, MOD) % MOD
		else:
			kthMinProductIndex = subtreeNodeCountsProductUpdateVals[0][1]
			kthMinProduct = subtreeNodeCountsProduct * (n - subtreeNodeCounts[kthMinProductIndex]) * pow(subtreeNodeCounts[kthMinProductIndex], MOD - 2, MOD) % MOD
		return (kthMinProductIndex, kthMinProduct)
	elif subtreeNodeCountsProductUpdateVals[0][0] == 1:
		kthMinProduct = subtreeNodeCountsProduct
		equalProductIndices = [nodeIndex]
		equalProductIndices += [subtreeNodeCountsProductUpdateVals[i][1] for i in range(min(len(subtreeNodeCountsProductUpdateVals), k)) if subtreeNodeCountsProductUpdateVals[i][0] == 1]
		equalProductIndices = sorted(equalProductIndices, reverse=True)
		return (equalProductIndices[k - 1], kthMinProduct)
	else:
		visitedNodes[nodeIndex] = True
		nextIndex = subtreeNodeCountsProductUpdateVals[0][1]
		subtreeNodeCountsProduct = subtreeNodeCountsProduct * (n - subtreeNodeCounts[nextIndex]) * pow(subtreeNodeCounts[nextIndex], MOD - 2, MOD) % MOD
		return findKthMinSubtreeNodeCountsProduct(adjNodes, n, k, subtreeNodeCounts, nextIndex, visitedNodes, subtreeNodeCountsProduct, nodeIndex)

def factorial(n):
	f = 1
	for i in range(1, n + 1):
		f = f * i % MOD
	return f

def solve(adjNodes, n, k):
	if n == 1:
		return (1, 2 - k)
	startIndex = 1
	subtreeNodeCounts = [1] * (n + 1)
	visitedNodes = [False] * (n + 1)
	populateSubtreeNodeCounts(adjNodes, n, subtreeNodeCounts, startIndex, visitedNodes)
	debug(subtreeNodeCounts)
	subtreeNodeCountsProduct = 1
	for i in range(1, n + 1):
		subtreeNodeCountsProduct = subtreeNodeCountsProduct * subtreeNodeCounts[i] % MOD
	debug(subtreeNodeCountsProduct)
	visitedNodes = [False] * (n + 1)
	(kthMinProductNodeIndex, kthMinProduct) = findKthMinSubtreeNodeCountsProduct(adjNodes, n, k, subtreeNodeCounts, startIndex, visitedNodes, subtreeNodeCountsProduct, 0)
	debug(kthMinProductNodeIndex, kthMinProduct)
	maxToplogicalOrderingsCount = factorial(n) * pow(kthMinProduct, MOD - 2, MOD) % MOD
	result = (kthMinProductNodeIndex, maxToplogicalOrderingsCount)
	return result
tc = int(input())
for t in range(tc):
	(n, k) = map(int, input().split())
	adjNodes = []
	for i in range(n + 1):
		adjNodes.append([])
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adjNodes[u].append(v)
		adjNodes[v].append(u)
	result = solve(adjNodes, n, k)
	print(*result)


from typing import List, Tuple
import sys

def mpow(x: int, p: int, m: int) -> int:
	if p == 0:
		return 1
	if p == 1:
		return x % m
	ans = mpow(x, p >> 1, m)
	ans = ans * ans % m
	if p & 1 == 1:
		ans = ans * x % m
	return ans

class Mod:

	def __init__(self):
		_max_idx = int(500000.0 + 5)
		_mod = int(1000000000.0 + 7)
		_f = [1] * _max_idx
		_fi = [1] * _max_idx
		for i in range(1, _max_idx):
			_f[i] = _f[i - 1] * i % _mod
		_fi[-1] = mpow(_f[_max_idx - 1], _mod - 2, _mod)
		for i in range(_max_idx - 2, 0, -1):
			_fi[i] = _fi[i + 1] * (i + 1) % _mod
		self.f = _f
		self.fi = _fi
		self.mod = _mod

def solve(n: int, k: int, g: List[List[int]], m: Mod) -> Tuple[int, int]:
	c = []
	size = [0] * (n + 1)

	def dfs(u: int, p: int):
		size[u] = 1
		is_centroid = True
		for v in g[u]:
			if v == p:
				continue
			dfs(v, u)
			size[u] += size[v]
			if size[v] > n // 2:
				is_centroid = False
		if n - size[u] > n // 2:
			is_centroid = False
		if is_centroid:
			c.append(u)
	dfs(1, 1)
	c.sort()

	def get_c(u: int, p: int) -> int:
		(w, vw, s) = (1, 1, 0)
		for v in g[u]:
			if v == p:
				continue
			vways = get_c(v, u)
			s += size[v]
			w = w * m.fi[size[v]] % m.mod
			vw = vw * vways % m.mod
		size[u] = s + 1
		vw = vw * w % m.mod
		return vw * m.f[s] % m.mod
	node = -1
	if k == 1:
		node = c[len(c) - 1]
	elif len(c) == 2:
		node = c[0]
	else:
		dfs(c[0], 0)
		node = g[c[0]][0]
		for v in g[c[0]]:
			if size[v] > size[node] or (size[v] == size[node] and v > node):
				node = v
	return (node, get_c(node, 0))

def main():
	sys.setrecursionlimit(int(500000.0 + 21))
	m = Mod()
	t = int(input())
	for _ in range(t):
		(n, k) = [int(x) for x in input().split()]
		g = [[] for _ in range(n + 1)]
		for _ in range(n - 1):
			(u, v) = [int(x) for x in input().split()]
			g[u].append(v)
			g[v].append(u)
		(i, c) = solve(n, k, g, m)
		print(f'{i} {c}')
main()


import sys
sys.setrecursionlimit(10 ** 6)

def dfs(u, p):
	global diff, prsz, pr, ch, chsz
	for i in a[u]:
		if i != p:
			dfs(i, u)
			b[u] += b[i]
	b[u] += 1
	x = abs(n - 2 * b[u])
	if u != 0 and x < diff:
		diff = x
		chsz = b[u]
		prsz = n - b[u]
		ch = u
		pr = p
	elif u != 0 and x == diff:
		if p == pr:
			ch = max(ch, u)

def dfs1(u, p):
	for i in a[u]:
		if i == p:
			continue
		dfs1(i, u)
		c[u] += c[i]
		dp[u] = dp[u] * dp[i] % mod
		dp[u] = dp[u] * inver[c[i]] % mod
	dp[u] = dp[u] * fact[c[u]] % mod
	c[u] += 1
mod = 10 ** 9 + 7
fact = [1] * 10 ** 6
inver = [1] * 10 ** 6

def inv(x):
	return pow(x, mod - 2, mod)
for i in range(2, 5 * 10 ** 5 + 5):
	fact[i] = fact[i - 1] * i % mod
	inver[i] = inv(fact[i])
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	if n == 1:
		print(1, 1)
		continue
	a = [[] for i in range(n)]
	xy = []
	diff = float('inf')
	chsz = -1
	prsz = -1
	ch = -1
	pr = -1
	k1 = -1
	k2 = -1
	for i in range(n - 1):
		(x, y) = list(map(int, input().split()))
		x -= 1
		y -= 1
		a[x].append(y)
		a[y].append(x)
	if n <= 10:
		ans = []
		for i in range(n):
			dp = [1] * n
			c = [0] * n
			dfs1(i, -1)
			ans.append([dp[i], i])
		ans.sort(reverse=True)
		print(ans[k - 1][1] + 1, ans[k - 1][0])
	else:
		b = [0] * n
		c = [0] * n
		dp = [1] * n
		dfs(0, -1)
		if prsz == chsz:
			k1 = max(pr, ch)
			k2 = min(pr, ch)
		elif prsz > chsz:
			k1 = pr
			k2 = ch
		else:
			k1 = ch
			k2 = pr
		if k == 1:
			dfs1(k1, -1)
			print(k1 + 1, dp[k1])
		else:
			dfs1(k2, -1)
			print(k2 + 1, dp[k2])


from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
FAC = [1]
for i in range(1, 10 ** 6):
	FAC.append(FAC[-1] * i % MOD)
XXX = 0

def dfs(G, x, P, MEM):
	if P in MEM[x]:
		return MEM[x][P]
	p = 1
	c = 1
	for i in G[x]:
		if i == P:
			continue
		(a, b) = dfs(G, i, x, MEM)
		c = (c + b) % MOD
		p = p * a % MOD
	MEM[x][P] = (p * c % MOD, c)
	return MEM[x][P]

def ch(G, x, P, C):
	if C[x]:
		return 0
	c = 1
	for i in G[x]:
		if i == P:
			continue
		c += ch(G, i, x, C)
	C[x] = c
	return C[x]

def main():
	for _ in range(int(input())):
		(N, K) = list(map(int, input().split()))
		G = [[] for _ in range(N)]
		for i in range(N - 1):
			(a, b) = list(map(int, input().split()))
			G[a - 1].append(b - 1)
			G[b - 1].append(a - 1)
		MEM = [{} for _ in range(N)]
		R = FAC[N]
		if N < 12:
			arr = [(dfs(G, i, -1, MEM)[0], -i - 1) for i in range(N)]
			arr.sort()
			L = arr[K - 1]
			S = R * pow(L[0], MOD - 2, MOD) % MOD
			print(-L[1], S)
			continue
		CH = [0] * N
		ch(G, 0, -1, CH)
		G2 = [0 for _ in range(N)]
		G3 = [[] for _ in range(N)]
		for i in range(len(G)):
			for j in G[i]:
				if i < j:
					continue
				if CH[i] < CH[j]:
					a = CH[i]
					b = N - a
				else:
					b = CH[j]
					a = N - b
				if a > b:
					G3[i].append(j)
					G2[j] += 1
				elif a < b:
					G3[j].append(i)
					G2[i] += 1
		X = []
		for i in range(N):
			if G2[i] == 0:
				X.append(i)
		X.sort(reverse=True)
		if len(X) >= K:
			MX = max(X)
			L = dfs(G, MX, -1, MEM)[0]
			S = R * pow(L, MOD - 2, MOD) % MOD
			print(MX + 1, S)
			continue
		X = X[0]
		Y = []
		for i in G3[X]:
			G2[i] -= 1
			if G2[i] == 0:
				j = X
				if CH[i] < CH[j]:
					a = CH[i]
					b = N - a
				else:
					b = CH[j]
					a = N - b
				Y.append((a / b, i))
		MX = max(Y)[1]
		L = dfs(G, MX, -1, MEM)[0]
		S = R * pow(L, MOD - 2, MOD) % MOD
		print(MX + 1, S)
main()


import sys
sys.setrecursionlimit(5 * 10 ** 5)
prime = 10 ** 9 + 7

def num_total_orderings(T, root):
	global accum, numerator_factor
	N = len(T)
	accum = 1
	numerator_factor = N
	S = [1] * (N + 1)

	def tracer(root, S, parent=None):
		global accum, numerator_factor
		for neighbor in T[root]:
			if neighbor != parent:
				tracer(neighbor, S, root)
				S[root] += S[neighbor]
		accum *= numerator_factor
		accum *= inverse(S[root])
		accum %= prime
		numerator_factor -= 1
	tracer(root, S)
	return (accum, S)

def centroid(T):
	n = len(T)
	S = num_total_orderings(T, 1)[1]

	def tracer(root, parent=None):
		for neighbor in T[root]:
			if neighbor != parent:
				if 2 * S[neighbor] == n:
					return max(root, neighbor)
				if 2 * S[neighbor] > n:
					return tracer(neighbor, root)
		return root
	return tracer(1)

def pow_mod(base, exponent, modulus):
	if exponent == 0:
		return 1
	sqrt = pow_mod(base, exponent // 2, modulus)
	ret = sqrt * sqrt
	if exponent % 2 == 1:
		ret *= base
	return ret % modulus
inverse_dict = dict()

def inverse(num):
	if num not in inverse_dict:
		inverse_dict[num] = pow_mod(num, prime - 2, prime)
	return inverse_dict[num]
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	T = {v: [] for v in range(1, N + 1)}
	for _ in range(N - 1):
		(v, w) = map(int, input().split())
		T[v].append(w)
		T[w].append(v)
	c = centroid(T)
	(num, S) = num_total_orderings(T, c)
	if K == 1:
		print(c, num)
	elif K == 2:
		v = max([(S[w], w) for w in T[c]])[1]
		print(v, num * S[v] * inverse(N - S[v]) % prime)