CF1725I.Imitating the Key Tree

Pak Chanek has a tree called the key tree. This tree consists of $N$ vertices and $N-1$ edges. The edges of the tree are numbered from $1$ to $N-1$ with edge $i$ connecting vertices $U_i$ and $V_i$. Initially, each edge of the key tree does not have a weight.

Formally, a path with length $k$ in a graph is a sequence $[v_1, e_1, v_2, e_2, v_3, e_3, \ldots, v_k, e_k, v_{k+1}]$ such that:

• For each $i$, $v_i$ is a vertex and $e_i$ is an edge.
• For each $i$, $e_i$ connects vertices $v_i$ and $v_{i+1}$.

A circuit is a path that starts and ends on the same vertex.

A path in a graph is said to be simple if and only if the path does not use the same edge more than once. Note that a simple path can use the same vertex more than once.

The cost of a simple path in a weighted graph is defined as the maximum weight of all edges it traverses.

Count the number of distinct undirected weighted graphs that satisfy the following conditions:

• The graph has $N$ vertices and $2N-2$ edges.
• For each pair of different vertices $(x, y)$, there exists a simple circuit that goes through vertices $x$ and $y$ in the graph.
• The weight of each edge in the graph is an integer between $1$ and $2N-2$ inclusive. Each edge has distinct weights.
• The graph is formed in a way such that there is a way to assign a weight $W_i$ to each edge $i$ in the key tree that satisfies the following conditions:
  • For each pair of edges $(i, j)$, if $i \lt j$, then $W_i \lt W_j$.
  • For each pair of different vertex indices $(x, y)$, the cost of the only simple path from vertex $x$ to $y$ in the key tree is equal to the minimum cost of a simple circuit that goes through vertices $x$ and $y$ in the graph.
• Note that the graph is allowed to have multi-edges, but is not allowed to have self-loops.

Print the answer modulo $998\,244\,353$.

Two graphs are considered distinct if and only if there exists a triple $(a, b, c)$ such that there exists an edge that connects vertices $a$ and $b$ with weight $c$ in one graph, but not in the other.

帕克·查内克有一棵名为“钥匙树”的树。这棵树包含 $N$ 个顶点和 $N-1$ 条边。树的边从 $1$ 编号到 $N-1$，其中第 $i$ 条边连接顶点 $U_i$ 和 $V_i$。初始时，钥匙树的每条边均无权重。

形式化地，图中一条长度为 $k$ 的路径是一个序列 $[v_1, e_1, v_2, e_2, v_3, e_3, \ldots, v_k, e_k, v_{k+1}]$，满足：

• 对每个 $i$，$v_i$ 是一个顶点，$e_i$ 是一条边；
• 对每个 $i$，$e_i$ 连接顶点 $v_i$ 和 $v_{i+1}$。

回路（circuit）是一条起点与终点为同一顶点的路径。

图中的一条路径被称为简单路径，当且仅当该路径不重复使用同一条边。注意：简单路径可以多次经过同一顶点。

在带权图中，一条简单路径的代价定义为该路径所经过的所有边中权重的最大值。

请计算满足以下条件的互不相同的无向带权图的数目：

• 该图有 $N$ 个顶点和 $2N-2$ 条边；
• 对任意一对不同的顶点 $(x, y)$，图中存在一条经过顶点 $x$ 和 $y$ 的简单回路；
• 图中每条边的权重均为 $1$ 到 $2N-2$（含端点）之间的整数，且所有边的权重互不相同；
• 该图的构造方式满足：存在一种为钥匙树中每条边 $i$ 分配权重 $W_i$ 的方法，使得：
  • 对任意两条边 $(i, j)$，若 $i < j$，则 $W_i < W_j$；
  • 对任意一对不同的顶点索引 $(x, y)$，钥匙树中从顶点 $x$ 到 $y$ 的唯一简单路径的代价，等于图中所有经过顶点 $x$ 和 $y$ 的简单回路的最小代价。
• 注意：图中允许存在重边，但不允许存在自环。

请将答案对 $998\,244\,353$ 取模后输出。

当且仅当存在一个三元组 $(a, b, c)$，使得某条连接顶点 $a$ 和 $b$、权重为 $c$ 的边在一个图中存在而在另一个图中不存在时，两个图被视为不同。

The first line contains a single integer $N$ ($2 \le N \le 10^5$) — the number of vertices in the key tree.

The $i$-th of the next $N-1$ lines contains two integers $U_i$ and $V_i$ ($1 \le U_i, V_i \le N$) — an edge connecting vertices $U_i$ and $V_i$. The graph in the input is a tree.

第一行包含一个整数 $N$（$2 \le N \le 10^5$）—— 表示密钥树中的顶点数量。

接下来的 $N-1$ 行中，第 $i$ 行包含两个整数 $U_i$ 和 $V_i$（$1 \le U_i, V_i \le N$）—— 表示连接顶点 $U_i$ 和 $V_i$ 的一条边。输入中的图是一棵树。

An integer representing the number of distinct undirected weighted graphs that satisfy the conditions of the problem modulo $998\,244\,353$.

一个整数，表示满足题目条件的不同无向带权图的数量对 $998\,244\,353$ 取模的结果。

The following is an example of a graph that satisfies.

The following is an assignment of edge weights in the key tree that corresponds to the graph above.

As an example, consider a pair of vertex indices $(1, 4)$.

• The circuit in the graph for this pair of vertices is $3 \xrightarrow{2} 2 \xrightarrow{4} 4 \xrightarrow{6} 2 \xrightarrow{1} 1 \xrightarrow{5} 3$ with a cost of $6$.
• The path in the key tree for this pair of vertices is $1 \xrightarrow{5} 3 \xrightarrow{6} 4$ with a cost of $6$.

以下是满足条件的一个图示例。

以下是与上述图相对应的密钥树（key tree）中各边的权重赋值。

以顶点索引对 $(1, 4)$ 为例：

• 该顶点对在图中的回路为 $3 \xrightarrow{2} 2 \xrightarrow{4} 4 \xrightarrow{6} 2 \xrightarrow{1} 1 \xrightarrow{5} 3$，总代价为 $6$。
• 该顶点对在密钥树中的路径为 $1 \xrightarrow{5} 3 \xrightarrow{6} 4$，总代价为 $6$。