Mandatory Passage

The campus is modeled as a connected undirected graph with \(n\) vertices and \(m\) edges (possibly with multiple edges but no self‐loops). The vertices are labeled from \(1\) to \(n\). The main gate is located at vertex \(1\), the computer room at vertex \(n\), and Professor Tu’s office at vertex \(z\) (with \(z\neq 1,n\)).

Before the contest begins, \(m-n+1\) edges are blocked such that the remaining graph (which still contains all \(n\) vertices) is connected and, in fact, becomes a tree (i.e. there is exactly one simple path between any two vertices). The blocking scheme is chosen uniformly at random among all possibilities (if \(m=n-1\), no edge is blocked).

wygz does not want Professor Tu’s office to lie on her only available path from the main gate to the computer room. Help her compute the probability that, after the blocking, the unique path from vertex \(1\) to vertex \(n\) must pass through vertex \(z\). Output your answer modulo \(998244353\).

Note on the approach

A key fact is that when a spanning tree is chosen uniformly at random from a connected graph, the unique path between two fixed vertices (here, \(1\) and \(n\)) has the same distribution as the loop-erased random walk from \(1\) to \(n\). In particular, the probability that a vertex \(v\) appears on this path is equal to the probability that a simple random walk starting from \(1\) reaches \(v\) before reaching \(n\) (with boundary conditions \(h(1)=1\) and \(h(n)=0\)).

For every vertex \(v\) with \(2\le v\le n-1\) (we denote this set as \(A\)), the corresponding harmonic function \(h(v)\) satisfies \[ \mathrm{deg}(v)\,h(v)-\sum_{u\in A}\;c_{vu}\,h(u)=\#\{\text{edges from }v\text{ to }1\}, \] where \(\mathrm{deg}(v)\) is the total degree of \(v\) and \(c_{vu}\) is the number of edges between \(v\) and \(u\). Solving this system modulo \(998244353\) yields \(h(v)\) for every \(v\in A\); in particular, the answer is \(h(z)\) when \(z\in A\) (and is \(1\) if \(z=1\) and \(0\) if \(z=n\)).

inputFormat

The first line contains three integers (n), (m), and (z) (with (3\le n); (n-1\le m); and (1<z<n)).

Then (m) lines follow, each containing two integers (u) and (v) ((1\le u,v\le n) and (u\neq v)), representing an undirected edge between vertices (u) and (v). There may be multiple edges between the same pair of vertices.

outputFormat

Output a single integer — the probability (modulo (998244353)) that the unique path from vertex (1) to vertex (n) passes through vertex (z).

sample

3 3 2
1 2
2 3
1 3

499122177