Counting Distinct Graphs Generated from a Special Tree

You are given a tree \(T\) with \(n\) nodes (numbered from \(1\) to \(n\)) and \(n-1\) edges. The edges are numbered from \(1\) to \(n-1\) in an arbitrary order. The tree \(T\) satisfies the following property: for any node \(u\), every vertex on the simple path from \(u\) to node \(n\) has a label \(\ge u\); in other words, the path from \(u\) to \(n\) does not contain any vertex with a number smaller than \(u\). This implies that \(T\) can be viewed as a rooted tree with node \(n\) as the unique maximum (root) and every non-root node \(u\) has a parent with a label greater than \(u\>.

Next, a graph \(G\) on \(n\) nodes is generated by the following procedure:

1. Select a permutation \(p\) of \(\{1,2,\dots, n-1\}\) (i.e. an ordering of the edges of \(T\)).
2. Perform \(n-1\) operations sequentially. In the \(i\)th operation, remove the edge numbered \(p_i\) from the current tree \(T\) (which becomes a forest) and let \(a\) and \(b\) be its endpoints. In the two connected components (in the current forest) that contain \(a\) and \(b\) respectively, let \(u\) and \(v\) be the maximum-numbered vertices. Then add an undirected edge between nodes \(u\) and \(v\) in \(G\>.

After all operations, the graph \(G\) has exactly \(n-1\) edges. Two graphs \(G_1\) and \(G_2\) are considered essentially different if there exists a pair \(u,v\) such that edge \((u,v)\) is present in one graph and absent in the other.

Your task is to compute the number of essentially different graphs \(G\) that can be obtained by applying the above procedure over all \((n-1)!\) permutations, modulo \(998244353\).

Observation and Hint: Due to the tree property, if you root the tree at node \(n\) the unique parent of a node \(u\) is the next vertex on the path from \(u\) to \(n\). Let \(s_u\) denote the size of the subtree rooted at \(u\) (including \(u\) itself). It turns out that the answer is the product of \(s_u\) over all nodes \(u \neq n\). That is, the answer is:

[ \prod_{u=1}^{n-1} s_u \pmod{998244353}. ]

Compute the subtree sizes by doing a DFS starting from node \(n\>, and then output the product modulo \(998244353\).

inputFormat

The first line contains a single integer \(n\) (\(1 \le n \le 2\times10^5\)). The next \(n-1\) lines each contain two integers \(u\) and \(v\) (\(1 \le u,v \le n\)), representing an edge in \(T\). It is guaranteed that \(T\) is a tree and satisfies the property that for any node \(u\), the simple path from \(u\) to \(n\) does not contain any vertex with a value less than \(u\).

outputFormat

Output the number of essentially different graphs \(G\) that can be produced by the procedure, modulo \(998244353\).

sample

2
1 2

1