Background

HQZ is tinkering with a machine made by LMX.

Problem Description

An undirected connected graph is defined to be good if and only if there exists an orientation of all edges such that the original graph can be turned into a directed acyclic graph in which only $S$ has in-degree $0$ and only $T$ has out-degree $0$.

Given an undirected connected graph with $n$ vertices and $m$ edges, with no self-loops, define one operation as choosing two (possibly identical) vertices $x, y$ uniformly at random with $x \le y$, and adding an edge between $x$ and $y$. Let $P$ be the probability that the graph after one operation is good. Output $P \bmod 998244353$.

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

If $P = 0$, you need to construct a plan that deletes the minimum number of vertices so that the original graph becomes good.

Input Format

The first line contains four positive integers $n, m, S, T$, as described above.

The next $m$ lines each contain two positive integers $x_i, y_i$, indicating an undirected edge between $x_i$ and $y_i$.

Output Format

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

If $P > 0$, output the next two lines. The first of these lines contains two positive integers $u, v$, indicating that the edge you add is the directed edge $u \to v$. The second line contains a string $s$ of length $m$ consisting only of $0$ and $1$. If $s_i = 0$, then the direction of edge $(x_i, y_i)$ is $x_i \to y_i$; otherwise it is $y_i \to x_i$.

If $P = 0$, output the next two lines. The first of these lines contains a positive integer $c$, indicating the minimum number of vertices to delete. The second line contains $c$ positive integers, indicating the vertices to delete.

Scoring:

If the output format is correct, then if your program correctly outputs the probability $P$, you will get $30\%$ of the score for that test point.

On top of that, if you also construct a correct plan, you will get $100\%$ of the score for that test point.

If your program has an incorrect output format, unexpected errors may occur.

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

Hint

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

update 7/27: Subtask #7 is new hack testdata. The constraints are the same as Subtask #6.

Translated by ChatGPT 5