Background

If you are not clear about some definitions in this problem, you can read the [Notes / Hint] section.

Problem Description

There is a tree $T$ with $n$ nodes, and all its edges are numbered from $1$ to $n-1$ in order.

It is guaranteed that for any node $u$ in $T$, the simple path from $u$ to node $n$ does not pass through any node whose index is less than $u$.

Generate an undirected graph $G$ with $n$ nodes by the following steps:

Choose a permutation $p$ of $1 \sim n-1$, and then perform $n-1$ operations in order. In the $i$-th operation, first delete the edge $(a,b)$ in tree $T$ whose index is $p_i$. Then let $u$ and $v$ be, respectively, the node with the largest index among all nodes currently connected to $a$ and to $b$ in the current tree $T$. Add an edge between node $u$ and node $v$ in graph $G$.

For the given tree $T$, find how many essentially different graphs $G$ can be generated in total by the method above. Graphs $G_1$ and $G_2$ are essentially different if and only if there exist $u$ and $v$ such that edge $(u,v)$ does not exist in $G_1$, but exists in $G_2$.

Since the answer may be very large, you only need to output it modulo $998244353$.

Input Format

The first line contains one integer $n$, the number of nodes in tree $T$.

The next $n-1$ lines each contain two integers $u, v$. In the $i$-th line, it means the edge in $T$ with index $i$ is $(u,v)$.

Output Format

Output one integer: the answer modulo $998244353$.

4
1 4
2 3
3 4

2

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

4605

Hint

【Help and Hint】

To make it easier for contestants to test their code, this problem additionally provides an extra sample for contestants to use.

Sample Input Sample Output

【Sample Explanation】

In sample 1, the possible graphs $G$ that can be generated are shown in the figure:

When $p = \{1,2,3\},\{2,1,3\},\{2,3,1\}$, the graph on the right will be generated; otherwise, the graph on the left will be generated.

For sample 2, I have a wonderful explanation, but unfortunately this blank space is too small to write it down.

【Constraints】

This problem uses bundled tests.

For all testdata, it is guaranteed that $1 \leq n \leq 3 \times 10^3$, $1 \leq u,v \leq n$.

It is guaranteed that the input edges form a tree, and for any node $u$, the simple path from $u$ to node $n$ does not pass through any node whose index is less than $u$.

Below are some definitions used in this problem:

• A tree is an undirected connected graph with $n$ nodes and $n-1$ edges.

• Edge $(u,v)$ means an edge connecting node $u$ and node $v$.

• A path is a sequence $p_1,p_2 \ldots p_k$ such that for any $1 \leq i < k$, edge $(p_i,p_{i+1})$ exists in $T$, and has not been deleted by previous operations.

• Nodes $u$ and $v$ are connected if and only if there exists a path $p_1,p_2 \ldots p_k$ such that $p_1=u$ and $p_k=v$. Every node is connected to itself.

Translated by ChatGPT 5