Problem Description

Lovely Tommy has a tree. In this tree, only vertices $a$ and $b$ are black, and all other vertices are white.

Each time, Tommy can recolor a black vertex $p$ to red, and then recolor all white vertices adjacent to $p$ into black. In the end, all vertices will be recolored to red.

Let the $i$-th vertex be recolored to red as the $t_i$-th one; then $t_i$ is a permutation of $1$ to $n$. Tommy wants you to help him find how many different $t_i$ there are.

Input Format

Each input file contains only one testdata.

• The first line contains three positive integers $n,a,b$ separated by spaces, representing the number of vertices of the tree and the indices of the initial black vertices.

• The next $n-1$ lines each contain two positive integers $x,y$, describing an edge $\left( x,y\right)$ in the tree.

The vertices of the tree are numbered starting from $1$.

Output Format

Output $1$ line:

• One integer, representing the number of different permutations $t_i$ modulo $998,244,353$.

4 1 2
1 2
2 3
3 4

4

Hint

Constraints

It is guaranteed that $a,b\le n\le 234,567$.

Copyright Information

From the 2018 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2018). Thanks to Pony.ai for supporting this contest.

Resources such as editorials can be found at https://github.com/wangyurzee7/THUPC2018.

Translated by ChatGPT 5