P7437 Meeting a Gentleman

Special cameo: wygz (Wuyou Princess). Every time wygz walks from the school gate to the computer lab, she tries her best to avoid Teacher “Butcher”. However, one day, she suddenly found that some doors actually had signs saying “Do not enter or exit through this door”!

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$.

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

#### 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: | Test Point ID | $n$ | $m$ | | :----------: | :----------: | :----------: | | $1$ | $=3$ | $\le 5$ | | $2$ | $=3$ | $\le 10^5$ | | $3,4$ | $=7$ | $\le 15$ | | $5,6$ | $=7$ | $\le 10^5$ | | $7$ | $=20$ | $=n-1$ | | $8,9$ | $=20$ | $=n$ | | $10,11,12$ | $=18$ | $\le 10^5$ | | $13,14,15,16$ | $=19$ | $\le 10^5$ | | $17,18,19,20$ | $=20$ | $\le 10^5$ | 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