Problem Background

HQZ is playing with a machine belonging to LMX.

Problem Description

An undirected connected graph is defined as good if and only if there exists a set of orientation schemes such that the graph can be transformed into a directed acyclic graph with only $S$ having an in-degree of $0$ and $T$ having an out-degree of $0$ by orienting each edge.

Given an undirected connected graph with $n$ vertices and $m$ edges without self-loops, define an operation as randomly selecting two non-distinct points $x, y$ where $x \le y$ and connecting $x$ and $y$. Calculate the probability $P$ that the graph becomes good after one operation, modulo $998244353$.

If $P > 0$, you need to construct an orientation scheme after adding one edge.

If $P = 0$, you need to construct a scheme with the minimum number of deletions such that the original graph is good.

Input Format

The first line contains four positive integers $n, m, S, T$, as described in the problem statement.

The next $m$ lines, each containing two positive integers $x_i, y_i$, indicate that there is an undirected edge between $x_i$ and $y_i$.

Output Format

The first line contains a non-negative integer $P$.

If $P > 0$, the next two lines, the first containing two positive integers $u, v$ indicating the added directed edge $u \to v$, and the second a string $s$ of length $m$ containing only $0$ and $1$, where $s_i = 0$ means the direction of edge $(x_i, y_i)$ is $x_i \to y_i$, otherwise $y_i \to x_i$.

If $P = 0$, the next two lines, the first containing a positive integer $c$ indicating the minimum number of points to delete, and the second containing $c$ positive integers indicating the points to be deleted.

Scoring Method:

Given the correct output format, if your program correctly answers the probability $P$, you will earn $30\%$ of the points for that test case.

On top of that, if you correctly construct the scheme, you will earn $100\%$ of the points for that test case.

If your program's output format is incorrect, unexpected errors may occur.

Sample Input and Output

Sample Input #1

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

Sample Output #1

665496236
1 2
00010000

Sample Input #2

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

Sample Output #2

0
3
2 3 4

Sample Input #3

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

Sample Output #3

0
4
2 6 8 9

Notes

For all data, $1 \le n, m \le 5 \times 10^5$.

Update 7/27: Subtask #7 is a new Hack data. The data range is the same as Subtask #6.

见题面 Input 部分

见题面 Output 部分