题目背景

友情客串：wygz（无忧公主）

wygz 每次从进校到机房，都要尽量避开“屠夫”老师。然而，有一天，她忽然发现一些门上居然贴了“请勿从此门进出”的标签！

题目描述

校园可以抽象成一张 $n$ 个点 $m$ 条无向边（可能有重边，无自环）的连通无向图，点从 $1$ 标号到 $n$。校门在 $1$ 号点，而机房在 $n$ 号点，屠老师的办公室在点 $z$（$z\ne 1,n$）。

然而，工作人员（其实是樱初音）封锁了其中的 $m-n+1$ 条边，使得剩余的图（包括所有点以及剩余的边）仍然连通，此时任意两点之间有且仅有一条简单路径。工作人员会等概率地选择一种封锁方案。（若 $m=n-1$ 则不封锁任何边，保持不变）

wygz 当然不希望屠老师的办公室出现在她的必经之路上。她希望你算出从校门到机房的路径必须经过屠老师的办公室的概率。答案对 $998244353$ 取模。

输入格式

第一行三个正整数 $n$、$m$ 和 $z$，表示点数、边数和屠老师的办公室的位置。

以下 $m$ 行，每行两个正整数 $u$、$v$，表示一条连接 $u$ 和 $v$ 的无向边。

输出格式

一行一个非负整数，表示答案对 $998244353$ 取模的结果。

4 5 2
1 2
1 3
2 3
2 4
3 4

374341633

6 8 4
1 2
1 3
2 3
2 4
2 5
4 5
4 6
5 6

374341633

提示

样例解释：

样例 #1：生成树共 $8$ 个，有 $5$ 个满足 $1$ 到 $4$ 经过 $2$。$\dfrac 5 8\equiv 374341633\pmod {998244353}$。

样例 #2：生成树共 $24$ 个，有 $15$ 个满足 $1$ 到 $6$ 经过 $4$。$\dfrac {15} {24}\equiv 374341633\pmod {998244353}$。

数据范围：

对 $100\%$ 的数据，$3\le n\le 20$，$n-1\le m\le 10^5$，$z\ne 1$ 且 $z\ne n$。

数据保证输入的图的生成树个数模 $998244353$ 非零。