Social Infrastructure Information Systems Division  Hitachi Programming Contest 2020 - Preserve Diameter

We have a tree G with N vertices numbered 1 to N. The i-th edge of G connects Vertex a_i and Vertex b_i.

Consider adding zero or more edges in G, and let H be the graph resulted.

Find the number of graphs H that satisfy the following conditions, modulo 998244353.

* H does not contain self-loops or multiple edges.
* The diameters of G and H are equal.
* For every pair of vertices in H that is not directly connected by an edge, the addition of an edge directly connecting them would reduce the diameter of the graph.

Constraints

* 3 \le N \le 2 \times 10^5
* 1 \le a_i, b_i \le N
* The given graph is a tree.

Input

Input is given from Standard Input in the following format:


N
a_1 b_1
\vdots
a_{N-1} b_{N-1}


Output

Print the answer.

Examples

Input

6
1 6
2 1
5 2
3 4
2 3


Output

3


Input

3
1 2
2 3


Output

1


Input

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


Output

27


Input

19
2 4
15 8
1 16
1 3
12 19
1 18
7 11
11 15
12 9
1 6
7 14
18 2
13 12
13 5
16 13
7 1
11 10
7 17


Output

78732

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
input = sys.stdin.readline
mod = 998244353
N = int(input())
E = [[] for i in range(N + 1)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	E[x].append(y)
	E[y].append(x)
Q = [1]
D = [-1] * (N + 1)
D[1] = 0
while Q:
	x = Q.pop()
	for to in E[x]:
		if D[to] == -1:
			D[to] = D[x] + 1
			Q.append(to)
f = D.index(max(D))
Q = [f]
D = [-1] * (N + 1)
D[f] = 0
while Q:
	x = Q.pop()
	for to in E[x]:
		if D[to] == -1:
			D[to] = D[x] + 1
			Q.append(to)
MAX = max(D)
l = D.index(MAX)
Q = [l]
D2 = [-1] * (N + 1)
D2[l] = 0
while Q:
	x = Q.pop()
	for to in E[x]:
		if D2[to] == -1:
			D2[to] = D2[x] + 1
			Q.append(to)
if MAX % 2 == 0:
	for i in range(N + 1):
		if D[i] == MAX // 2 and D2[i] == MAX // 2:
			c = i
			break
	TOP_SORT = []
	Q = [c]
	D = [-1] * (N + 1)
	P = [-1] * (N + 1)
	D[c] = 0
	while Q:
		x = Q.pop()
		TOP_SORT.append(x)
		for to in E[x]:
			if D[to] == -1:
				D[to] = D[x] + 1
				Q.append(to)
				P[to] = x
	DP = [[[0, 0, 0] for i in range(3)] for i in range(N + 1)]
	for x in TOP_SORT[::-1]:
		if D[x] == MAX // 2:
			DP[x][1][1] = 1
		elif len(E[x]) == 1:
			DP[x][0][0] = 1
		else:
			for to in E[x]:
				if to == P[x]:
					continue
				X = [[0, 0, 0] for i in range(3)]
				for i in range(3):
					for j in range(3):
						X[0][0] += DP[to][i][j]
						X[i][0] += DP[to][i][j]
						X[0][j] += DP[to][i][j]
				if DP[x] == [[0, 0, 0] for i in range(3)]:
					DP[x] = X
				else:
					Y = [[0, 0, 0] for i in range(3)]
					for i in range(3):
						for j in range(3):
							for k in range(3):
								for l in range(3):
									Y[min(2, i + k)][min(2, j + l)] = (Y[min(2, i + k)][min(2, j + l)] + X[i][j] * DP[x][k][l]) % mod
					DP[x] = Y
	print(DP[c][1][1] * pow(2, mod - 2, mod) % mod)
else:
	for i in range(N + 1):
		if D[i] == MAX // 2 and D2[i] == MAX // 2 + 1:
			c1 = i
		elif D[i] == MAX // 2 + 1 and D2[i] == MAX // 2:
			c2 = i
	TOP_SORT = []
	Q = [c1, c2]
	D = [-1] * (N + 1)
	P = [-1] * (N + 1)
	D[c1] = 0
	D[c2] = 0
	P[c1] = c2
	P[c2] = c1
	while Q:
		x = Q.pop()
		TOP_SORT.append(x)
		for to in E[x]:
			if D[to] == -1:
				D[to] = D[x] + 1
				Q.append(to)
				P[to] = x
	DP = [[[0, 0, 0] for i in range(3)] for i in range(N + 1)]
	for x in TOP_SORT[::-1]:
		if D[x] == MAX // 2:
			DP[x][1][1] = 1
		elif len(E[x]) == 1:
			DP[x][0][0] = 1
		else:
			for to in E[x]:
				if to == P[x]:
					continue
				X = [[0, 0, 0] for i in range(3)]
				for i in range(3):
					for j in range(3):
						X[0][0] += DP[to][i][j]
						X[i][0] += DP[to][i][j]
						X[0][j] += DP[to][i][j]
				if DP[x] == [[0, 0, 0] for i in range(3)]:
					DP[x] = X
				else:
					Y = [[0, 0, 0] for i in range(3)]
					for i in range(3):
						for j in range(3):
							for k in range(3):
								for l in range(3):
									Y[min(2, i + k)][min(2, j + l)] = (Y[min(2, i + k)][min(2, j + l)] + X[i][j] * DP[x][k][l]) % mod
					DP[x] = Y
	print(sum(DP[c1][1]) * sum(DP[c2][1]) % mod)