[THUPC2018] 淘米神的树
题目描述
可爱的 Tommy 有一棵树。这棵树上只有点 $a$ 和 $b$ 是黑色,其它的点都是白色。
每次,Tommy 可以将一个黑色 $p$ 的点染成红色,然后把和 $p$ 相邻的所有白色的点染成黑色。最后,所有的点都会被染成红色。
设第 $i$ 个点是第 $t_i$ 个被染成红色的,那么 $t_i$ 是一个 $1$ 到 $n$ 的排列。Tommy 希望你帮他求出,有多少种不同的 $t_i$。
输入输出格式
输入格式
每个输入文件仅包含一个测试数据。
* 第一行三个用空格隔开的正整数 $n,a,b$,表示树的点数和初始的黑色点的编号;
* 接下来 $n-1$ 行,每行两个正整数 $x,y$ 描述树上的一条边 $\left( x,y\right)$。
树上的节点从 $1$ 开始编号。
输出格式
输出 $1$ 行:
* 一个整数,表示不同的排列 $t_i$ 的个数除以 $998,244,353$ 的余数。
输入输出样例
输入样例 #1
4 1 2
1 2
2 3
3 4
输出样例 #1
4
说明
### 数据范围
保证 $a,b\le n\le 234,567$。
### 版权信息
来自 2018 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2018),感谢 [Pony.ai](http://pony.ai/) 对此次比赛的支持。
题解等资源可在 <https://github.com/wangyurzee7/THUPC2018> 查看。