P10809 [LMXOI Round 2] Nirvana

HQZ is tinkering with a machine made by LMX.

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.

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$.

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.**

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.** | Subtask # | $n$ | $m$ | Special Property | Score | | :-------: | :-----------------: | :-----------------: | :-------------------------: | :---: | | Subtask #1 | $\le 10$ | $\le 10$ | None | $25$ | | Subtask #2 | $\le 500$ | $= n - 1$ | $x_i = i, y_i = i + 1$ | $10$ | | Subtask #3 | $\le 5 \times 10^5$ | $= n$ | The original graph is a cycle | $5$ | | Subtask #4 | $\le 500$ | $\le 500$ | None | $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$ | None | $20$ | Translated by ChatGPT 5