题目背景

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\%$ 的分数。

若你的程序输出格式错误，可能会出现不可预料的错误。

5 8 1 4
1 2
2 3
3 4
4 5
1 3
1 4
2 4
3 5

665496236
1 2
00010000

6 5 5 6
1 2
1 3
1 4
1 5
1 6

0
3
2 3 4

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

0
4
2 6 8 9

提示

对于所有数据，$1 \le n, m \le 5 \times 10^5$。

update 7/27: Subtask #7 为新的 Hack 数据。数据范围同 Subtask #6。