Nauuo is a girl who loves drawing circles.

One day she has drawn a circle and wanted to draw a tree on it.

The tree is a connected undirected graph consisting of $n$ nodes and $n-1$ edges. The nodes are numbered from $1$ to $n$.

Nauuo wants to draw a tree on the circle, the nodes of the tree should be in $n$ distinct points on the circle, and the edges should be straight without crossing each other.

"Without crossing each other" means that every two edges have no common point or the only common point is an endpoint of both edges.

Nauuo wants to draw the tree using a permutation of $n$ elements. A permutation of $n$ elements is a sequence of integers $p_1,p_2,\ldots,p_n$ in which every integer from $1$ to $n$ appears exactly once.

After a permutation is chosen Nauuo draws the $i$-th node in the $p_i$-th point on the circle, then draws the edges connecting the nodes.

The tree is given, Nauuo wants to know how many permutations are there so that the tree drawn satisfies the rule (the edges are straight without crossing each other). She only wants to know the answer modulo $998244353$, can you help her?

It is obvious that whether a permutation is valid or not does not depend on which $n$ points on the circle are chosen.


-----Input-----

The first line contains a single integer $n$ ($2\le n\le 2\cdot 10^5$) — the number of nodes in the tree.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1\le u,v\le n$), denoting there is an edge between $u$ and $v$.

It is guaranteed that the given edges form a tree.


-----Output-----

The output contains a single integer — the number of permutations suitable to draw the given tree on a circle satisfying the rule, modulo $998244353$.


-----Examples-----
Input
4
1 2
1 3
2 4

Output
16
Input
4
1 2
1 3
1 4

Output
24


-----Note-----

Example 1

All valid permutations and their spanning trees are as follows.

[Image]

Here is an example of invalid permutation: the edges $(1,3)$ and $(2,4)$ are crossed.

[Image]

Example 2

Every permutation leads to a valid tree, so the answer is $4! = 24$.

Difficulty: HARD
Tags: Tree algorithms

Combinatorics

Graph traversal

Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
g = [0] * 200005
r = int(input())
n = r
for i in range(1, n):
	(u, v) = map(int, input().split())
	g[u] += 1
	g[v] += 1
	r *= g[u] * g[v]
	r %= 998244353
print(r)


n = int(input())
r = n
MAX = 998244353
arr = [0] * (n + 1)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	arr[a] += 1
	arr[b] += 1
	r *= arr[a] * arr[b]
	r %= MAX
print(r)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def YES():
	print('YES')

def NO():
	print('NO')

def Yes():
	print('Yes')

def No():
	print('No')
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24
tot = 200005
mod = 998244353
fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
for i in range(2, tot + 1):
	fac.append(fac[-1] * i % mod)
	inv.append(mod - inv[mod % i] * (mod // i) % mod)
	finv.append(finv[-1] * inv[-1] % mod)

def comb(n, r):
	if n < r:
		return 0
	else:
		return fac[n] * (finv[r] * finv[n - r] % mod) % mod

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		self.num_sets -= 1
		self.parent[a] = b
		self.size[b] += self.size[a]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def lcm(a, b):
	return abs(a // gcd(a, b) * b)

def solve():
	mod = 998244353
	n = N()
	deg = [0] * n
	for _ in range(n - 1):
		(a, b) = sep()
		a -= 1
		b -= 1
		deg[a] += 1
		deg[b] += 1
	p = 1
	for i in range(n):
		p *= fac[deg[i]]
		p %= mod
	print(n * p % mod)
solve()


import sys
input = sys.stdin.buffer.readline
mod = 998244353
ans = 1
n = int(input())
adj = [0] * (n + 1)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	adj[a] += 1
	adj[b] += 1
fact = [1] * n
for i in range(2, n):
	fact[i] = fact[i - 1] * i % mod
for i in adj[1:]:
	ans = ans * fact[i] % mod
print(n * ans % mod)


n = int(input())
g = [0] * n
m = 998244353
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a - 1] += 1
	g[b - 1] += 1
fact = [1]
for i in range(1, n):
	fact.append(fact[-1] * i % m)
for i in g:
	n = n * fact[i] % m
print(n)


mod = 998244353
n = int(input())
deg = [0] * (n + 1)
fac = [1] * (n + 1)
for i in range(1, n + 1):
	fac[i] = fac[i - 1] * i % mod
for i in range(n - 1):
	(a, b) = list(map(int, input().split()))
	deg[a] += 1
	deg[b] += 1
s = 1
for i in range(1, n + 1):
	s = s * fac[deg[i]] % mod
s = s * n % mod
print(s)


import sys
input = sys.stdin.readline
MOD = 998244353
fa = [1]
for i in range(1, 2 * 10 ** 5 + 10):
	fa.append(fa[-1] * i % MOD)
N = int(input())
X = [[] for i in range(N)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	X[x - 1].append(y - 1)
	X[y - 1].append(x - 1)
P = [-1] * N
Q = [0]
while Q:
	i = Q.pop()
	for a in X[i]:
		if a != P[i]:
			P[a] = i
			X[a].remove(i)
			Q.append(a)
ans = N
for i in range(len(X)):
	ans = ans * fa[len(X[i]) + (1 if i else 0)] % MOD
print(ans)


import sys
n = int(sys.stdin.readline().strip())
D = [0] * n
p = 998244353
for i in range(0, n - 1):
	(u, v) = list(map(int, sys.stdin.readline().strip().split()))
	D[u - 1] = D[u - 1] + 1
	D[v - 1] = D[v - 1] + 1
ans = n
for i in range(0, n):
	for j in range(0, D[i]):
		ans = ans * (j + 1) % p
print(ans)


n = int(input())
m = n
g = [0] * 200005
for i in range(n - 1):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	g[a] += 1
	g[b] += 1
	m = m * g[a] * g[b] % 998244353
print(m)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def main():
	n = I()
	aa = [LI() for _ in range(n - 1)]
	e = collections.defaultdict(set)
	for (a, b) in aa:
		e[a].add(b)
		e[b].add(a)
	q = [[(1, -1)]]
	qi = 0
	while 1:
		t = q[qi]
		nq = []
		for (i, p) in t:
			for c in e[i]:
				if c == p:
					continue
				nq.append((c, i))
		if len(nq) < 1:
			break
		q.append(nq)
		qi += 1
	gm = [1]
	for i in range(1, n + 1):
		gm.append(i * gm[-1] % mod)
	m = {}

	def f(i, p):
		t = 1
		r = 1
		for c in e[i]:
			if c == p:
				continue
			r *= m[c]
			r %= mod
			t += 1
		if p == -1:
			r *= gm[t - 1]
			r *= n
		else:
			r *= gm[t]
		r %= mod
		m[i] = r
		return r
	for qt in q[::-1]:
		for (i, p) in qt:
			f(i, p)
	r = f(1, -1)
	return r
print(main())


import sys
from collections import deque
mod = 998244353
frac = [1] * 364364
for i in range(2, 364364):
	frac[i] = i * frac[i - 1] % mod
N = int(input())
Dim = [0] * N
Edge = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, sys.stdin.readline().split())
	a -= 1
	b -= 1
	Dim[a] += 1
	Dim[b] += 1
	Edge[a].append(b)
	Edge[b].append(a)
Dim[0] += 1
par = [-1] + [0] * (N - 1)
stack = [0]
visited = set([0])
while stack:
	vn = stack.pop()
	for vf in Edge[vn]:
		if vf in visited:
			continue
		visited.add(vf)
		par[vf] = vn
		stack.append(vf)
leaf = [i for i in range(N) if Dim[i] == 1]
D = Dim[:]
dp = [1] * N
Q = deque(leaf)
while Q:
	vn = Q.pop()
	if vn == 0:
		dp[vn] = dp[vn] * frac[Dim[vn] - 1] % mod
		break
	dp[vn] = dp[vn] * frac[Dim[vn]] % mod
	vp = par[vn]
	D[vp] -= 1
	dp[vp] = dp[vp] * dp[vn] % mod
	if D[vp] == 1:
		Q.appendleft(vp)
print(N * dp[0] % mod)


import sys

def topological_sort_tree(E, p):
	Q = [p]
	L = []
	visited = set([p])
	while Q:
		p = Q.pop()
		L.append(p)
		for vf in E[p]:
			if vf not in visited:
				visited.add(vf)
				Q.append(vf)
	return L

def getpar(Edge, p):
	N = len(Edge)
	par = [0] * N
	par[p] -= 1
	stack = [p]
	visited = set([p])
	while stack:
		vn = stack.pop()
		for vf in Edge[vn]:
			if vf in visited:
				continue
			visited.add(vf)
			par[vf] = vn
			stack.append(vf)
	return par
mod = 998244353
frac = [1] * 364364
for i in range(2, 364364):
	frac[i] = i * frac[i - 1] % mod
N = int(input())
Dim = [0] * N
Edge = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, sys.stdin.readline().split())
	a -= 1
	b -= 1
	Dim[a] += 1
	Dim[b] += 1
	Edge[a].append(b)
	Edge[b].append(a)
L = topological_sort_tree(Edge, 0)
P = getpar(Edge, 0)
dp = [1] * N
for l in L[::-1]:
	dp[l] = dp[l] * frac[Dim[l]] % mod
	dp[P[l]] = dp[P[l]] * dp[l] % mod
print(N * dp[0] % mod)


import math

def factorial(n, j):
	inf = 998244353
	j[0] = 1
	j[1] = 1
	for i in range(2, n + 1):
		j[i] = j[i - 1] * i
		j[i] %= inf
	return j
l1 = [0] * 200009
y = factorial(200008, l1)
inf = 998244353
n = int(input())
l = [0] * 200009
x = 1
for i in range(n - 1):
	(u, v) = input().split()
	(u, v) = [int(u), int(v)]
	l[u] += 1
	l[v] += 1
for i in range(len(l)):
	if l[i] > 0:
		x *= y[l[i]]
		x %= inf
print(n * x % inf)


import io, os
g = [0] * 200005
r = int(input())
n = r
for i in range(1, n):
	(u, v) = list(map(int, input().split()))
	g[u] += 1
	g[v] += 1
	r *= g[u] * g[v]
	r %= 998244353
print(r)


p = 998244353
n = int(input())
facs = [1]
for i in range(1, n):
	facs.append(facs[-1] * i % p)
graph = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	graph[u - 1].append(v - 1)
	graph[v - 1].append(u - 1)
prod = facs[len(graph[0])] * n
for i in range(1, n):
	k = len(graph[i])
	prod = prod * facs[k] % p
print(prod)


import sys
input = sys.stdin.readline
n = int(input())
fr = [0] * (n + 2)
fr[0] = 1
d = [0] * (n + 2)
mod = int(998244353)
for i in range(1, n + 1):
	fr[i] = fr[i - 1] * i % mod
for i in range(n - 1):
	(u, v) = map(int, input().split())
	d[u] += 1
	d[v] += 1
ans = n
for i in range(1, n + 1):
	ans = ans * fr[d[i]]
	ans %= mod
print(ans)


import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main():
	N = 10 ** 6
	mod = 998244353
	fac = [1] * (N + 1)
	finv = [1] * (N + 1)
	for i in range(N):
		fac[i + 1] = fac[i] * (i + 1) % mod
	finv[-1] = pow(fac[-1], mod - 2, mod)
	for i in reversed(range(N)):
		finv[i] = finv[i + 1] * (i + 1) % mod

	def cmb1(n, r, mod):
		if r < 0 or r > n:
			return 0
		r = min(r, n - r)
		return fac[n] * finv[r] * finv[n - r] % mod
	n = int(input())
	g = [[] for i in range(n)]
	ind = [0] * n
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		(u, v) = (u - 1, v - 1)
		g[u].append(v)
		g[v].append(u)
		ind[u] += 1
		ind[v] += 1
	M = max(ind)
	for i in range(n):
		if ind[i] == M:
			s = i
			break
	stack = []
	stack.append(s)
	depth = [-1] * n
	depth[s] = 0
	par = [-1] * n
	order = []
	while stack:
		v = stack.pop()
		order.append(v)
		for u in g[v]:
			if u == par[v]:
				continue
			depth[u] = depth[v] + 1
			par[u] = v
			stack.append(u)
	C = [1] * n
	order.reverse()
	for v in order:
		if par[v] != -1:
			C[par[v]] += 1
	dp = [1] * n
	for v in order:
		if par[v] != -1:
			dp[v] *= fac[C[v]]
			dp[v] %= mod
			dp[par[v]] *= dp[v]
			dp[par[v]] %= mod
		else:
			dp[v] *= n
			dp[v] *= fac[C[v] - 1]
	print(dp[s] % mod)
main()


from math import *
from collections import *
import sys
sys.setrecursionlimit(10 ** 9)
mod = 998244353
n = int(input())
a = [0 for i in range(n + 1)]
ans = n
for i in range(n - 1):
	(u, v) = map(int, input().split())
	a[u] += 1
	a[v] += 1
	ans *= a[u]
	ans %= mod
	ans *= a[v]
	ans %= mod
print(ans % mod)


n = int(input())
d = [0] * (n + 1)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	d[u] += 1
	d[v] += 1
	n = n * d[u] * d[v] % 998244353
print(n)


from sys import stdin, exit
from collections import defaultdict
input = stdin.readline
n = int(input())
edge = [tuple(map(int, line.split())) for line in stdin.read().splitlines()]
res = n
d = defaultdict(int)
MOD = 998244353
for (u, v) in edge:
	d[u] += 1
	d[v] += 1
	res = res * d[u] % MOD * d[v] % MOD
print(res)


from collections import Counter
n = int(input())
f = [1]
for i in range(1, n):
	f.append(f[-1] * i % 998244353)
d = []
for _ in range(n - 1):
	d.extend(input().split())
res = n
for v in Counter(d).values():
	res *= f[v]
	res %= 998244353
print(res)


import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
MOD = 998244353
tree = [[] for i in range(n)]
for i in range(n - 1):
	tree[info[i][0] - 1].append(info[i][1] - 1)
	tree[info[i][1] - 1].append(info[i][0] - 1)
ans = 1
for i in range(1, n + 1):
	ans *= i
	ans %= MOD
q = deque()
q.append([0, -1])
visited = [False] * n
visited[0] = True
cnt = 0
par = [0] * n
while q:
	(pos, par_pos) = q.popleft()
	if cnt == 0:
		cnt += 1
	else:
		par[par_pos] += 1
		par[pos] += 1
		ans *= 1 - (cnt - par[par_pos]) * pow(cnt, MOD - 2, MOD)
		cnt += 1
		ans %= MOD
	for i in tree[pos]:
		if not visited[i]:
			visited[i] = True
			q.append([i, pos])
print(ans)


MOD = 998244353

def main():
	buf = input()
	n = int(buf)
	edge = dict()
	for i in range(n):
		edge[i] = []
	for i in range(n - 1):
		buf = input()
		buflist = list(buf.split())
		a = int(buflist[0]) - 1
		b = int(buflist[1]) - 1
		edge[a].append(b)
		edge[b].append(a)
	pow2 = [1]
	factorial = [1]
	for i in range(1, n + 1):
		pow2.append(pow2[-1] * 2 % MOD)
		factorial.append(factorial[-1] * i % MOD)
	root = 0
	for v in edge:
		if len(edge[v]) == 1:
			root = v
			break
	visited = []
	for i in range(n):
		visited.append(False)
	stack = [root]
	from_root = True
	permutation = 1
	path_length = 0
	while stack:
		current = stack.pop()
		visited[current] = True
		if len(edge[current]) == 1:
			if current == root:
				stack.append(edge[current][0])
			else:
				permutation = permutation * pow2[path_length] % MOD
				path_length = 0
		elif len(edge[current]) == 2:
			path_length += 1
			for adj in edge[current]:
				if not visited[adj]:
					stack.append(adj)
		else:
			permutation = permutation * pow2[path_length] % MOD
			path_length = 0
			permutation = permutation * factorial[len(edge[current])] % MOD
			for adj in edge[current]:
				if not visited[adj]:
					stack.append(adj)
	permutation = permutation * n % MOD
	print(permutation)
main()


fact = []
M = 998244353
for i in range(200007):
	fact.append(0)
fact[0] = 1
for i in range(1, 200004):
	fact[i] = fact[i - 1] * i
	fact[i] %= M
n = int(input())
g = []
for i in range(0, n + 2):
	g.append([])
for i in range(n - 1):
	(x, y) = map(int, input().split())
	g[x].append(y)
	g[y].append(x)
ans = n
for i in range(n + 1):
	ans *= fact[len(g[i])]
	ans %= M
ans += M
ans %= M
print(ans)


import sys
n = int(input())
E = [list(map(int, input().split())) for i in range(n - 1)]
mod = 998244353
ELIST = [[] for i in range(n + 1)]
for (a, b) in E:
	ELIST[a].append(b)
	ELIST[b].append(a)
MUR = [1]
for i in range(1, n + 1):
	MUR.append(MUR[-1] * i % mod)
ANS = 1
for i in range(1, n + 1):
	ANS = ANS * MUR[len(ELIST[i])] % mod
print(ANS * n % mod)


from collections import defaultdict
mod = 998244353
fak = [1]
n = int(input())
for i in range(1, n + 1):
	fak.append(fak[i - 1] * i % mod)
d = defaultdict(int)
for i in range(n - 1):
	(x, y) = map(int, input().split())
	d[x] += 1
	d[y] += 1
ans = n
for i in d:
	ans *= fak[d[i]]
	ans %= mod
print(ans)


n = int(input())
mod = 998244353
gt = [1, 1]
for i in range(2, 200000):
	gt.append(i * gt[-1] % mod)
g = {}
p = {i: -1 for i in range(1, n + 1)}
dp = {}
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	if u not in g:
		g[u] = []
	if v not in g:
		g[v] = []
	g[u].append(v)
	g[v].append(u)
i = 0
S = [1]
p[1] = 0
while i < len(S):
	cur = S[i]
	for next_n in g[cur]:
		if next_n == p[cur]:
			continue
		p[next_n] = cur
		S.append(next_n)
	i += 1
for x in S[1:][::-1]:
	if len(g[x]) == 1:
		dp[x] = 1
	else:
		tmp = 1
		for next_n in g[x]:
			if next_n == p[x]:
				continue
			tmp = tmp * dp[next_n] % mod
		tmp = tmp * gt[len(g[x])] % mod
		if x == 1:
			tmp = n * tmp % mod
		dp[x] = tmp
dp[1] = n * gt[len(g[1])] % mod
for x in g[1]:
	dp[1] = dp[1] * dp[x] % mod
print(dp[1])


import sys
input = sys.stdin.readline
N = int(input())
e = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(u, v) = map(int, input().split())
	e[u].append(v)
	e[v].append(u)
mod = 998244353

class Factorial:

	def __init__(self, n, mod):
		self.f = [1]
		for i in range(1, n + 1):
			self.f.append(self.f[-1] * i % mod)
		self.i = [pow(self.f[-1], mod - 2, mod)]
		for i in range(1, n + 1)[::-1]:
			self.i.append(self.i[-1] * i % mod)
		self.i.reverse()

	def factorial(self, i):
		return self.f[i]

	def ifactorial(self, i):
		return self.i[i]

	def combi(self, n, k):
		return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(N, mod)
s = [1]
order = []
parent = [0] * (N + 1)
children = [1] * (N + 1)
children[1] = 0
vis = [0] * (N + 1)
while len(s):
	x = s.pop()
	vis[x] = 1
	order.append(x)
	for y in e[x]:
		if vis[y]:
			continue
		s.append(y)
		parent[y] = x
		children[x] += 1
order.reverse()
dp = [1] * (N + 1)
for y in order:
	x = parent[y]
	dp[x] *= dp[y] * f.factorial(children[y])
	dp[x] %= mod
print(dp[0] * N % mod)