Score : $600$ points
We have a graph $G$ with $N$ vertices numbered $1$ through $N$ and $0$ edges. You are given sequences $u=(u_1,u_2,\ldots,u_M),v=(v_1,v_2,\ldots,v_M)$ of length $M$.
You will perform the following operation $(N-1)$ times.
Note that the operation above will add a new edge connecting Vertices $u_i$ and $v_i$ even if $G$ already has one or more edges between them. In other words, the resulting $G$ may contain multiple edges.
For each $K=1,2,\ldots,N-1$, find the probability, modulo $998244353$, that $G$ is a forest after the $K$-th operation.
An undirected graph without a cycle is called a forest. A forest is not necessarily connected.
We can prove that the sought probability is always a rational number. Moreover, under the Constraints of this problem, it is guaranteed that, when the sought probability is represented by an irreducible fraction $\frac{y}{x}$, $x$ is indivisible by $998244353$.
Then, we can uniquely determine an integer $z$ between $0$ and $998244352$ (inclusive) such that $xz \equiv y \pmod{998244353}$. Print this $z$.
Input is given from Standard Input in the following format:
$N$ $M$ $u_1$ $v_1$ $\vdots$ $u_M$ $v_M$
Print $N-1$ lines. The $i$-th line should contain the probability, modulo $998244353$, that $G$ is a forest after the $i$-th operation.
3 2 1 2 2 3
1 499122177
Let us denote by $(u, v)$ the edge connecting Vertices $u$ and $v$.
After the $1$-st operation, $G$ will have:
In both cases, $G$ is a forest, so the answer for $K=1$ is $1$.
After the $2$-nd operation, $G$ will have:
$G$ is a forest only when $G$ has Edges $(1, 2)$ and $(2, 3)$. Therefore, the sought probability is $1/2$; when represented modulo $998244353$, it is $499122177$, which should be printed.
4 5 1 2 1 2 1 4 2 3 2 4
1 758665709 918384805