Description

The campus can be seen as a connected undirected graph with $n$ vertices and $m$ undirected edges (multiple edges may exist, no self-loops). The vertices are numbered from $1$ to $n$. The school gate is at vertex $1$, the computer lab is at vertex $n$, and Teacher Tu’s office is at vertex $z$ ($z\ne 1,n$).

However, staff members (actually Sakura Hatsune) block $m-n+1$ of the edges, so that the remaining graph (including all vertices and the remaining edges) is still connected. At this time, between any two vertices there is exactly one simple path. The staff will choose a blocking plan uniformly at random. (If $m=n-1$, then no edges are blocked and the graph stays unchanged.)

Of course, wygz does not want Teacher Tu’s office to appear on her unavoidable route. Please compute the probability that the path from the school gate to the computer lab must pass through Teacher Tu’s office. Output the answer modulo $998244353$.

Input Format

The first line contains three positive integers $n$, $m$, and $z$, representing the number of vertices, the number of edges, and the location of Teacher Tu’s office.

The next $m$ lines each contain two positive integers $u$, $v$, indicating an undirected edge connecting $u$ and $v$.

Output Format

Output one line with one non-negative integer, representing the answer modulo $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

Hint

Sample Explanation:

Sample #1: There are $8$ spanning trees in total, and $5$ of them satisfy that the path from $1$ to $4$ passes through $2$. $\dfrac 5 8\equiv 374341633\pmod {998244353}$.

Sample #2: There are $24$ spanning trees in total, and $15$ of them satisfy that the path from $1$ to $6$ passes through $4$. $\dfrac {15} {24}\equiv 374341633\pmod {998244353}$.

Constraints:

For $100\%$ of the testdata, $3\le n\le 20$, $n-1\le m\le 10^5$, $z\ne 1$ and $z\ne n$.

The testdata guarantees that the number of spanning trees of the input graph modulo $998244353$ is non-zero.

Translated by ChatGPT 5