P10809 [LMXOI Round 2] Nirvana

HQZ 在摆弄 LMX 的一台机器。

定义一张无向连通图是**好的**，当且仅当存在一组定向方案使得原图可以通过对每条边定向使其成为仅有 $S$ 入度为 $0$，$T$ 出度为 $0$ 的**有向无环**图。 给定一张 $n$ 个点 $m$ 条边**无自环**的**无向连通图**，定义一次操作为等概率选取两个**可重**的点 $x, y$ 且 $x \le y$，连接 $x$ 和 $y$。求一次操作后的图是**好的**的概率 $P$ 对 $998244353$ 取模的值。 若 $P > 0$，你需要在加入一条边后构造一组定向方案。 若 $P = 0$，你需要构造一组删点数量最少的方案使得原图是好的。

第一行四个正整数 $n, m, S, T$，含义如题面所述。 接下来 $m$ 行，第 $i$ 行两个正整数 $x_i,y_i$，表示 $x_i$ 和 $y_i$ 之间有一条无向边。

第一行一个非负整数 $P$。 若 $P > 0$，接下来两行，第一行两个正整数 $u, v$ 表示你添加的边为 $u \to v$（有向），第二行一个长度为 $m$ 的仅包含 $0$ 和 $1$ 的字符串 $s$，$s_i = 0$ 表示 $(x_i, y_i)$ 这条边的方向为 $x_i \to y_i$，否则为 $y_i \to x_i$。 若 $P = 0$，接下来输出两行，第一行包含一个正整数 $c$，表示最少要删除多少个点。第二行包含 $c$ 个正整数，表示需要删掉的点。 **评分方式：** **在输出格式正确的情况下**，若你的程序正确回答了概率 $P$，则你能获得该测试点 $30\%$ 的分数。 **在此基础上**，若你正确构造出了方案，则你能获得该测试点 $100\%$ 的分数。 **若你的程序输出格式错误，可能会出现不可预料的错误。**

对于所有数据，$1 \le n, m \le 5 \times 10^5$。 **update 7/27: Subtask #7 为新的 Hack 数据。数据范围同 Subtask #6**。 | 子任务编号 | $n$ | $m$ | 特殊性质 | 分值 | | :--------: | :-----------------: | :-----------------: | :--------------------: | :--: | | Subtask #1 | $\le 10$ | $\le 10$ | 无 | $25$ | | Subtask #2 | $\le 500$ | $= n - 1$ | $x_i = i, y_i = i + 1$ | $10$ | | Subtask #3 | $\le 5 \times 10^5$ | $= n$ | 原图是一个环 | $5$ | | Subtask #4 | $\le 500$ | $\le 500$ | 无 | $20$ | | Subtask #5 | $\le 5 \times 10^5$ | $= n - 1$ | $x_i = i, y_i = i + 1$ | $20$ | | Subtask #6 | $\le 5 \times 10^5$ | $\le 5 \times 10^5$ | 无 | $20$ |