Description

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?

Input Format

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 Format

Output one integer on one line, representing the answer.

Please take the result modulo $998244353$.

8 8 1 10
1 2
1 3
1 4
2 5
3 5
5 6
6 7
6 8

6

3 2 1 3
1 2
1 3

332748119

Hint

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<v_i$, $s=1$.
• Subtask 3 (30 pts): $n,m \le 10^3$.
• Subtask 4 (40 pts): no special restrictions.

For $100\%$ of the testdata, $1 \le n,m \le 5 \times 10^6$, $1 \le s \le n$, $1 \le u_i,v_i \le n$, $u_i \ne v_i$, $n \le p \le 10^9$.

Translated by ChatGPT 5