Good Graph Orientation and Minimal Deletion

An undirected connected graph with n vertices and m edges (with no self‐loops) is called good if and only if there exists an orientation of every edge which makes the graph a directed acyclic graph (DAG) with exactly one vertex S having indegree 0 and exactly one vertex T having outdegree 0. In other words, one can assign a direction to every edge so that the resulting graph is acyclic and has a unique source and a unique sink.

You are given an undirected connected graph with n vertices and m edges. Then one operation is performed: two (not necessarily distinct) vertices x and y with x ≤ y are chosen uniformly at random (note that repeated choices are allowed), and an edge connecting x and y is added to the graph. Let P be the probability that, after this single operation, the resulting graph is good. Report P mod 998244353.

There are two cases:

1. If P > 0: You must not only print P mod 998244353 but also construct an orientation for all edges (including the newly added edge) so that the resulting graph is a DAG with a unique source and a unique sink. (In our output format, the orientation is given by printing each directed edge as a pair u v meaning an edge directed from u to v.)
2. If P = 0: You must construct a minimum deletion set, i.e. remove as few vertices as possible so that the induced subgraph of the remaining vertices is good. Output the number of deleted vertices k and the list of deleted vertices (in increasing order).

Important: If P > 0, you are allowed to choose any extra edge (among the possibilities that keep the probability positive) and any valid orientation that satisfies the conditions. If P = 0, any minimum deletion set is acceptable.

Note (in LaTeX):

The graph is good if and only if there exists an orientation such that the resulting graph is a DAG and only one vertex has indegree $0$ and only one vertex has outdegree $0$. Equivalently, there exists a permutation $p=[p_1,p_2,\dots,p_n]$ of vertices such that for every consecutive pair $(p_i,p_{i+1})$, the edge exists (or can be added) and by orienting all edges in accordance with this order (i.e. from lower to higher index), the desired property holds. In the case where the original graph is missing exactly one edge between some consecutive pair, you can complete the Hamiltonian path by adding that extra edge.

The probability P is calculated as follows (in the case P > 0):

$$P = \frac{\#\{\text{favorable pairs } (x,y) \text{ with } x<y\}}{\#\{\text{all pairs } (x,y) \text{ with } x \le y\}} = \frac{\frac{n(n-1)}{2}}{\frac{n(n+1)}{2}} = \frac{n-1}{n+1}. $$

Compute this fraction modulo $998244353$, i.e. output $(n-1) \cdot (n+1)^{-1} \bmod 998244353$.

inputFormat

The input consists of multiple lines:

1. The first line contains two integers n and m ($2 \le n \le 10^5$, $m \ge 1$), representing the number of vertices and edges, respectively.
2. The following m lines each contain two integers u and v ($1 \le u, v \le n$, u ≠ v), representing an undirected edge between vertices u and v. It is guaranteed that the graph is connected and there are no self‐loops.

Note: In the random operation, a pair of vertices (x, y) with x &le y is chosen uniformly from all $\frac{n(n+1)}{2}$ possible pairs; self-loops (when x = y) are allowed in the choice, although adding a self-loop would yield a cycle.

outputFormat

If P > 0, then the output should be:

1. The first line contains an integer representing P mod 998244353.
2. The next m+1 lines each contain two integers u and v, indicating a directed edge from vertex u to vertex v in a valid orientation of the graph after adding the extra edge.

If P = 0, then the output should be:

1. The first line is 0.
2. The second line contains an integer k — the minimum number of vertices to be removed.
3. The third line contains k space‐separated integers in increasing order representing the vertices to remove.

sample

3 2
1 2
2 3

499122177
1 2
2 3
1 3

</p>