p02752 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
```python
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)]
    # DP[x][p][m]で, plusのものが0個, 1個, 2個以上, minusのものが0個, 1個, 2個以上

    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)
    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)]
    # DP[x][p][m]で, plusのものが0個, 1個, 2個以上, minusのものが0個, 1個, 2個以上

    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[c1])
    #print(DP[c2])
    print(sum(DP[c1][1])*sum(DP[c2][1])%mod)
```