P7845 「dWoi R2」Change / 改造

入间改造对人类生存繁殖有帮助的工具（~~就是性能工具，具体可以去看看弹丸论破 V3 自由时间与入间美兔的交谈，在这里不方便说吧，毕竟是 青 少 年 编 程 网 站~~）玩腻了，她发现了有一个很 符 合 她 胃 口 的东西，叫做 Galgame，于是她开始打一款叫做 Little Busters 的 Galgame，然后沉迷上了沙耶线最后的场景。 --- 

在经过 $99$ 次的 Replay 后，沙耶终于发现迷宫是一个有向无环图。为了保证最后一次 Replay 的趣味性，时风瞬给沙耶和理树安排了一个小游戏。 这张有向无环图 $G$ 有 $n$ 个点，$m$ 条边，每条边的长度为 $1$。设 $l_i$ 为初始点 $s$ 到第 $i$ 条边所指向的点 $u$ 的最短路，定义第 $i$ 条边的边权为 $p-l_i$。游戏步骤是这样的（所有选择都是按如下顺序进行，并且每个人的选择都是公开的）。 1. 理树站在点 $s$ 上。 2. 时风瞬会随机选取一个点作为 $t$（$t$ 可以等于 $s$）。 3. 如果无法从 $s$ 到达 $t$，游戏直接结束。 3. 沙耶需要选择一条边。 4. 理树需要找到一条从 $s$ 到 $t$ 的路径。 5. 若沙耶选择的边在理树所选择的路径上，则理树就会将这条边的边权的钱给沙耶。 理树希望能少输钱，沙耶希望能多拿钱。若两方都采取最优策略，请问沙耶期望能得到多少钱。

第一行四个整数 $n,m,s,p$，分别代表有向图点数，边数与理树站在的位置，以及题目中出现的 $p$。 接下来 $m$ 行每行两个整数 $u_i,v_i$ 描述一条边。

一行一个整数代表答案。 请对 $998244353$ 取模。

#### 样例 1 解释 比如 $t=6$ 时，沙耶应该选择连接 $5,6$ 的那条边；$t=8$ 时，沙耶仍然应该选择连接 $5,6$ 的那条边；$t=4$ 时，应该选择连接 $1,4$ 的那条边；$t=5$ 时，沙耶无论选择什么边都不会得到钱。 设 $res_u$ 表示 $t=u$ 时沙耶能获得的最大收益，我们有 $res=\{0,9,9,9,0,7,7,7\}$。 #### 样例 2 解释 设 $res_u$ 表示 $t=u$ 时沙耶能获得的最大收益，我们有 $res=\{0,2,2\}$。 --- #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（10 pts）：$n,m \le 5$； - Subtask 2（20 pts）：$m=n-1$，$u_i