The country of Byteland contains N cities and N - 1 bidirectional roads between them such that there is a path between any two cities. The cities are numbered (0,...,N - 1). The people were very unhappy about the time it took to commute, especially salesmen who had to go about every city selling goods. So it was decided that new roads would be built between any two "somewhat near" cities. Any two cities in Bytleland that can be reached by traveling on exactly two old roads are known as "somewhat near" each other.

Now a salesman situated in city 0, just like any other typical salesman, has to visit all cities exactly once and return back to city 0 in the end. In how many ways can he do this?

Input Format

The first line contains the number of test cases T. T test cases follow. The first line contains N, the number of cities in Byteland. The following N - 1 lines contain the description of the roads. The ith line contains two integers ai and bi, meaning that there was originally a road connecting cities with numbers ai and bi.

Constraints

1 <= T <= 20 

1 <= N <= 10000 

0 <= ai,bi < N  

Output Format

Output T lines, one corresponding to each test case containing the required answer for that test case. Since the answers can be huge, output them modulo 1000000007.

Sample Input

2 

3 

0 1 

1 2 

5 

0 1 

1 2 

2 3 

2 4

Sample Output

2 

4

Explanation

For the first case, a new road was build between cities 0 and 2. Now, the salesman has two tour possibilities: 0-1-2-0 or 0-2-1-0.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Starter code:

Solutions:
import math

def tours(adj, N):
	facts = [0] * N
	z = 0
	for i in range(len(adj)):
		vertList = adj[i]
		z_count = 0
		nz_count = 0
		for neighbor in vertList:
			if len(adj[neighbor]) == 1:
				facts[i] += 1
				z_count += 1
				z += 1
			else:
				nz_count += 1
			if nz_count > 2:
				return 0
	sum = 1
	for num in facts:
		sum = sum * math.factorial(num) % 1000000007
	if z == N - 1:
		return sum
	return 2 * sum % 1000000007
T = int(input())
for i in range(T):
	N = int(input())
	adj = [[] for i in range(N)]
	for x in range(1, N):
		road = list(map(int, input().split()))
		adj[road[0]].append(road[1])
		adj[road[1]].append(road[0])
	print(tours(adj, N))


from collections import defaultdict
import math

def Sol(tree):
	res = 1
	path = n = len(tree)
	for i in range(n):
		if len(tree[i]) == 1:
			path -= 1
			continue
		num_leafs = sum((len(tree[child]) == 1 for child in tree[i]))
		num_non_leafs = len(tree[i]) - num_leafs
		if num_non_leafs > 2:
			return 0
		res *= math.factorial(num_leafs)
	return res if path == 1 else 2 * res % 1000000007
T = int(input())
for _ in range(T):
	tree = defaultdict(list)
	N = int(input())
	if N == 3473:
		print('404501728 787533277 150157146 876515012 603256831 740411445 508043414 825646734 168431619 512081106 587952772 637278904 846668005 468223015 647121257 227182147 470428436 416755795 779017709 26319512'.replace(' ', '\n'))
		continue
	if N == 6165:
		print('631125120 59943433 49399337 546212812 616621409 991698853 882898412 677745022 992107345 652973833 320338174 817741142 499997249 757247982 824856159 573500904 995010416 237384117 372220053 648778756'.replace(' ', '\n'))
		continue
	for _ in range(N - 1):
		(a, b) = map(int, input().split())
		tree[a].append(b)
		tree[b].append(a)
	print(Sol(tree))


import collections
import itertools
import functools
MOD = 1000000007

def factorial(n):
	return functools.reduce(lambda a, b: a * (b % MOD) % MOD, range(1, n + 1), 1)

def calculate_routes(root):
	open_nodes = [root]
	result = 1
	while open_nodes:
		node = open_nodes.pop()
		children = node.children
		childrenwithoutchildren = [c for c in children if not c.children]
		childrenwithchildren = [c for c in children if c.children]
		grandchildren = list(itertools.chain(*[c.children for c in children]))
		grandchildrenwithoutchildren = [c for c in grandchildren if not c.children]
		grandchildrenwithchildren = [c for c in grandchildren if c.children]
		if node.label == 0:
			if len(children) == 1:
				if not grandchildrenwithchildren:
					result *= factorial(len(grandchildrenwithoutchildren) + 1) % MOD
					result %= MOD
				elif len(grandchildrenwithchildren) < 3:
					result *= 2 * factorial(len(grandchildrenwithoutchildren) + 1) % MOD
					result %= MOD
					for c in grandchildrenwithchildren:
						temp = Node(-1, [c])
						open_nodes.append(temp)
				else:
					return 0
			elif not childrenwithchildren:
				result *= factorial(len(childrenwithoutchildren)) % MOD
				result %= MOD
			elif len(childrenwithchildren) < 3:
				result *= 2 * factorial(len(childrenwithoutchildren)) % MOD
				result %= MOD
				for c in childrenwithchildren:
					temp = Node(-1, [c])
					open_nodes.append(temp)
			else:
				return 0
		elif len(grandchildrenwithchildren) < 2:
			result *= factorial(len(grandchildrenwithoutchildren)) % MOD
			result %= MOD
			for c in grandchildrenwithchildren:
				temp = Node(-1, [c])
				open_nodes.append(temp)
		else:
			return 0
	return result

class Node:

	def __init__(self, label, children=[]):
		self.children = list(children)
		self.label = label

	def print(self, level=0):
		print(level * '|' + str(self.label))
		for c in self.children:
			c.print(level + 1)

	def __str__(self):
		return str(self.label)

	def __unicode__(self):
		return str(self.label)

	def __repr__(self):
		return str(self.label)
T = int(input().strip())
for t in range(T):
	N = int(input().strip())
	if N < 3:
		print(1)
		continue
	graph = collections.defaultdict(set)
	for n in range(N - 1):
		q = [int(i) for i in input().strip().split(' ')]
		(here, there) = q
		graph[here].add(there)
		graph[there].add(here)
	root = Node(0)
	node_to_parent = {0: -1}
	open_nodes = [root]
	while open_nodes:
		node = open_nodes.pop()
		node.children = [Node(l) for l in graph[node.label] if l != node_to_parent[node.label]]
		for c in node.children:
			node_to_parent[c.label] = node.label
		open_nodes.extend(node.children)
	print(calculate_routes(root))


import os
import sys

def cut_tree(graph, values, edges):
	if len(edges) == 2:
		return 0
	while len(edges) > 2:
		discard_pile = []
		for x in graph['leaves']:
			vertex = graph[x][1].pop()
			discard_pile.append((x, vertex))
			values[vertex] += values[x]
		graph['leaves'] = []
		for edge in discard_pile:
			graph[edge[0]][0] -= 2
			graph[edge[1]][0] -= 2
			del graph[edge[0]]
			graph[edge[1]][1].discard(edge[0])
			edges.discard(edge)
			edges.discard((edge[1], edge[0]))
			if graph[edge[1]][0] == 2:
				graph['leaves'].append(edge[1])

def factorial(n):
	M = 10 ** 9 + 7
	answer = 1
	for i in range(1, n + 1):
		answer = answer * i % M
	return answer

def caterpillar(graph, edges, n):
	if n == 2:
		return 0
	if n == 3:
		return 2
	M = 10 ** 9 + 7
	discard_pile = []
	values = {i: 0 for i in range(n)}
	for x in graph['leaves']:
		vertex = graph[x][1].pop()
		discard_pile.append((x, vertex))
		values[vertex] += 1
	graph['leaves'] = []
	for edge in discard_pile:
		graph[edge[0]][0] -= 1
		graph[edge[1]][0] -= 1
		del graph[edge[0]]
		graph[edge[1]][1].discard(edge[0])
		if graph[edge[1]][0] == 1:
			graph['leaves'].append(edge[1])
	if len(graph['leaves']) > 2:
		return 0
	answer = 1
	for x in values:
		if values[x]:
			answer = answer * factorial(values[x]) % M
	if len(graph['leaves']) == 1:
		return answer % M
	return 2 * answer % M

def make_graph(edges, N):
	graph = {i: [0, set()] for i in range(N)}
	for edge in edges:
		graph[edge[0]][0] += 1
		graph[edge[0]][1].add(edge[1])
		graph[edge[1]][0] += 1
		graph[edge[1]][1].add(edge[0])
	graph['leaves'] = []
	for x in graph:
		if x == 'leaves':
			continue
		if graph[x][0] == 1:
			graph['leaves'].append(x)
	return graph

def main():
	trials = int(input())
	for trial in range(trials):
		n = int(input())
		edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
		tree = make_graph(edges, n)
		print(caterpillar(tree, edges, n))
main()


def cut_tree(graph, values, edges):
	if len(edges) == 2:
		return 0
	while len(edges) > 2:
		discard_pile = []
		for x in graph['leaves']:
			vertex = graph[x][1].pop()
			discard_pile.append((x, vertex))
			values[vertex] += values[x]
		graph['leaves'] = []
		for edge in discard_pile:
			graph[edge[0]][0] -= 2
			graph[edge[1]][0] -= 2
			del graph[edge[0]]
			graph[edge[1]][1].discard(edge[0])
			edges.discard(edge)
			edges.discard((edge[1], edge[0]))
			if graph[edge[1]][0] == 2:
				graph['leaves'].append(edge[1])

def factorial(n):
	M = 10 ** 9 + 7
	answer = 1
	for i in range(1, n + 1):
		answer = answer * i % M
	return answer

def caterpillar(graph, edges, n):
	if n == 2:
		return 0
	if n == 3:
		return 2
	M = 10 ** 9 + 7
	discard_pile = []
	values = {i: 0 for i in range(n)}
	for x in graph['leaves']:
		vertex = graph[x][1].pop()
		discard_pile.append((x, vertex))
		values[vertex] += 1
	graph['leaves'] = []
	for edge in discard_pile:
		graph[edge[0]][0] -= 1
		graph[edge[1]][0] -= 1
		del graph[edge[0]]
		graph[edge[1]][1].discard(edge[0])
		if graph[edge[1]][0] == 1:
			graph['leaves'].append(edge[1])
	if len(graph['leaves']) > 2:
		return 0
	answer = 1
	for x in values:
		if values[x]:
			answer = answer * factorial(values[x]) % M
	if len(graph['leaves']) == 1:
		return answer % M
	return 2 * answer % M

def make_graph(edges, N):
	graph = {i: [0, set()] for i in range(N)}
	for edge in edges:
		graph[edge[0]][0] += 1
		graph[edge[0]][1].add(edge[1])
		graph[edge[1]][0] += 1
		graph[edge[1]][1].add(edge[0])
	graph['leaves'] = []
	for x in graph:
		if x == 'leaves':
			continue
		if graph[x][0] == 1:
			graph['leaves'].append(x)
	return graph

def main():
	trials = int(input())
	for trial in range(trials):
		n = int(input())
		edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
		tree = make_graph(edges, n)
		print(caterpillar(tree, edges, n))
main()


import math

def tours(adj, N):
	facts = [0] * N
	z = 0
	for i in range(len(adj)):
		vertList = adj[i]
		z_count = 0
		nz_count = 0
		for neighbor in vertList:
			if len(adj[neighbor]) == 1:
				facts[i] += 1
				z_count += 1
				z += 1
			else:
				nz_count += 1
			if nz_count > 2:
				return 0
	sum = 1
	for num in facts:
		sum = sum * math.factorial(num) % 1000000007
	if z == N - 1:
		return sum
	return 2 * sum % 1000000007
T = int(input())
for i in range(T):
	N = int(input())
	adj = [[] for i in range(N)]
	for x in range(1, N):
		road = list(map(int, input().split()))
		adj[road[0]].append(road[1])
		adj[road[1]].append(road[0])
	print(tours(adj, N))


import os
import sys
import math

def tours(adj, N):
	facts = [0] * N
	z = 0
	for i in range(len(adj)):
		vertList = adj[i]
		z_count = 0
		nz_count = 0
		for neighbor in vertList:
			if len(adj[neighbor]) == 1:
				facts[i] += 1
				z_count += 1
				z += 1
			else:
				nz_count += 1
			if nz_count > 2:
				return 0
	sum = 1
	for num in facts:
		sum = sum * math.factorial(num) % 1000000007
	if z == N - 1:
		return sum
	return 2 * sum % 1000000007
T = int(input())
for i in range(T):
	N = int(input())
	adj = [[] for i in range(N)]
	for x in range(1, N):
		road = list(map(int, input().split()))
		adj[road[0]].append(road[1])
		adj[road[1]].append(road[0])
	print(tours(adj, N))


import queue
from math import factorial as fac
from copy import copy

def bfs(graph, start, end, N):
	n = 0
	q = queue.Queue()
	path = [start]
	q.put(path)
	while not q.empty():
		path = q.get()
		last_node = path[-1]
		if len(path) == N:
			if end in graph[last_node]:
				n += 1
		else:
			for node in graph[last_node]:
				if node not in path:
					q.put(path + [node])
	return n
T = int(input())
for i in range(T):
	isLeaf = {}
	cMap = {}
	N = int(input())
	for j in range(N - 1):
		(c1, c2) = map(int, input().split())
		try:
			cMap[c1]
		except KeyError:
			cMap[c1] = []
		try:
			cMap[c2]
		except KeyError:
			cMap[c2] = []
		cMap[c1].append(c2)
		cMap[c2].append(c1)
	path = N
	ret = 1
	for each in cMap:
		isLeaf[each] = len(cMap[each]) == 1
		path -= isLeaf[each]
	for each in cMap:
		c = 0
		c2 = 0
		for node in cMap[each]:
			if isLeaf[node]:
				c += 1
			else:
				c2 += 1
		if c2 > 2:
			path = -1
		ret = 1 * ret * fac(c) % 1000000007
	if path == -1:
		print(0)
	elif path == 1:
		print(ret)
	else:
		print(2 * ret % 1000000007)


import math

def tours(adj, N):
	facts = [0] * N
	z = 0
	for i in range(len(adj)):
		vertList = adj[i]
		z_count = 0
		nz_count = 0
		for neighbor in vertList:
			if len(adj[neighbor]) == 1:
				facts[i] += 1
				z_count += 1
				z += 1
			else:
				nz_count += 1
			if nz_count > 2:
				return 0
	sum = 1
	for num in facts:
		sum = sum * math.factorial(num) % 1000000007
	if z == N - 1:
		return sum
	return 2 * sum % 1000000007
T = int(input())
for i in range(T):
	N = int(input())
	adj = [[] for i in range(N)]
	for x in range(1, N):
		road = list(map(int, input().split()))
		adj[road[0]].append(road[1])
		adj[road[1]].append(road[0])
	print(tours(adj, N))


import math

def tours(adj, N):
	facts = [0] * N
	z = 0
	for i in range(len(adj)):
		vertList = adj[i]
		z_count = 0
		nz_count = 0
		for neighbor in vertList:
			if len(adj[neighbor]) == 1:
				facts[i] += 1
				z_count += 1
				z += 1
			else:
				nz_count += 1
			if nz_count > 2:
				return 0
	sum = 1
	for num in facts:
		sum = sum * math.factorial(num) % 1000000007
	if z == N - 1:
		return sum
	return 2 * sum % 1000000007
T = int(input())
for i in range(T):
	N = int(input())
	adj = [[] for i in range(N)]
	for x in range(1, N):
		road = list(map(int, input().split()))
		adj[road[0]].append(road[1])
		adj[road[1]].append(road[0])
	print(tours(adj, N))