P7845 「dWoi R2」Change / Transformation

Iruma has gotten tired of modifying tools that help humans survive and reproduce (~~basically “performance tools”; you can check the conversations with Iruma Miu during free time in Danganronpa V3, but it is not convenient to talk about it here after all, since this is a teen programming website~~). She then discovered something that fits her taste very well, called Galgame. So she started playing a Galgame called Little Busters, and became obsessed with the final scene of Saya’s route. --- 

After $99$ Replays, Saya finally realized that the maze is a directed acyclic graph. To ensure the fun of the last Replay, Tokikaze Jun arranged a mini-game for Saya and Riki. This directed acyclic graph $G$ has $n$ vertices and $m$ edges, and each edge has length $1$. Let $l_i$ be the shortest path length from the starting vertex $s$ to the vertex $u$ pointed to by the $i$-th edge. Define the weight of the $i$-th edge as $p-l_i$. The game proceeds as follows (all choices are made in the order below, and everyone’s choices are public): 1. Riki stands at vertex $s$. 2. Tokikaze Jun randomly selects a vertex as $t$ ($t$ may be equal to $s$). 3. If $t$ is not reachable from $s$, the game ends immediately. 4. Saya needs to choose an edge. 5. Riki needs to find a path from $s$ to $t$. 6. If the edge chosen by Saya lies on the path chosen by Riki, then Riki will pay Saya the amount equal to the edge weight of that edge. Riki wants to lose as little money as possible, while Saya wants to get as much money as possible. If both sides play optimally, what is the expected amount of money that Saya can obtain?

The first line contains four integers $n,m,s,p$, representing the number of vertices and edges of the directed graph, the vertex where Riki stands, and the $p$ appearing in the statement. The next $m$ lines each contain two integers $u_i,v_i$, describing an edge.

Output one integer on one line, representing the answer. Please take the result modulo $998244353$.

#### Explanation of Sample 1 For example, when $t=6$, Saya should choose the edge connecting $5,6$; when $t=8$, Saya should still choose the edge connecting $5,6$; when $t=4$, she should choose the edge connecting $1,4$; when $t=5$, no matter which edge Saya chooses, she will not get any money. Let $res_u$ denote the maximum profit Saya can obtain when $t=u$. Then we have $res=\{0,9,9,9,0,7,7,7\}$. #### Explanation of Sample 2 Let $res_u$ denote the maximum profit Saya can obtain when $t=u$. Then we have $res=\{0,2,2\}$. --- #### Constraints and Notes **This problem uses bundled testdata.** - Subtask 1 (10 pts): $n,m \le 5$. - Subtask 2 (20 pts): $m=n-1$, $u_i