Sleeping Journey - Repovive Standard Round 5 | Repovive

14D. Sleeping Journey

2000 pts2s256 MB

You are given a connected undirected graph with $n$ vertices and $m$ edges.

You start at vertex $1$ and want to reach vertex $n$ .

Each day, you may choose exactly one of the following actions:

Move through one edge incident to your current vertex. This takes $1$ day.
Sleep. Sleeping takes $1$ day, and after that you wake up at one vertex chosen uniformly at random among all $n$ vertices.

You may choose your strategy adaptively, depending on the vertex where you are currently located.

For each test case, find the minimum possible expected number of days needed to reach vertex $n$ .

The answer can be represented as a rational number $\frac{P}{Q}$ . Output $P \times Q^{-1}$ modulo $998244353$ , where $Q^{-1}$ is the modular inverse of $Q$ modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$n - 1 \le m \le 2 \times 10^5$
The graph is connected.
There are no self-loops or multiple edges.
The sum of $n$ over all test cases is at most $2 \times 10^5$ .
The sum of $m$ over all test cases is at most $2 \times 10^5$ .

Input

The first line contains one integer $t$ .

Then $t$ test cases follow. Each test case has the following format:

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

Each edge connects vertices $u_i$ and $v_i$ .

Output

For each test case, output one integer: the minimum expected number of days modulo $998244353$ .

Samples

Input

Explanation

One possible optimal strategy is to sleep at vertex $1$ . After one day, you wake up uniformly at one of the $4$ vertices. If you wake up at vertex $4$ , you are already done. If you wake up at vertex $3$ , move to vertex $4$ in one more day. If you wake up at vertex $2$ , move through vertices $3$ and $4$ in two more days. If you wake up at vertex $1$ , use the same strategy again.

If the expected number of days is $E$ , then $E = 1 + \frac{E + 2 + 1 + 0}{4}$ , so $E = \frac{7}{3}$ . The printed value is $7 \times 3^{-1}$ modulo $998244353$ .

Output

332748120

Input

Case 1

2 1
1 2

Case 2

3 2
1 2
2 3

Case 3

Case 4

Explanation

Case 1

$1$

Case 2

$2$

Case 3

$1$

Case 4

$\frac{8}{3}$

Output

Case 1

Case 2

Case 3

Case 4

665496238

You are given a connected undirected graph with $n$ vertices and $m$ edges.

You start at vertex $1$ and want to reach vertex $n$ .

Each day, you may choose exactly one of the following actions:

Move through one edge incident to your current vertex. This takes $1$ day.
Sleep. Sleeping takes $1$ day, and after that you wake up at one vertex chosen uniformly at random among all $n$ vertices.

You may choose your strategy adaptively, depending on the vertex where you are currently located.

For each test case, find the minimum possible expected number of days needed to reach vertex $n$ .

The answer can be represented as a rational number $\frac{P}{Q}$ . Output $P \times Q^{-1}$ modulo $998244353$ , where $Q^{-1}$ is the modular inverse of $Q$ modulo $998244353$ .

$1 \le t \le 10^4$
$2 \le n \le 2 \times 10^5$
$n - 1 \le m \le 2 \times 10^5$
The graph is connected.
There are no self-loops or multiple edges.
The sum of $n$ over all test cases is at most $2 \times 10^5$ .
The sum of $m$ over all test cases is at most $2 \times 10^5$ .

The first line contains one integer $t$ .

Then $t$ test cases follow. Each test case has the following format:

\begin{array}{l} n \quad m \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_m \quad v_m \end{array}

Each edge connects vertices $u_i$ and $v_i$ .

For each test case, output one integer: the minimum expected number of days modulo $998244353$ .

If the expected number of days is $E$ , then $E = 1 + \frac{E + 2 + 1 + 0}{4}$ , so $E = \frac{7}{3}$ . The printed value is $7 \times 3^{-1}$ modulo $998244353$ .

$1$

$2$

$1$

$\frac{8}{3}$

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

14D. Sleeping Journey

Constraints

Input

Output

Samples

14D. Sleeping Journey

Constraints

Input

Output

Samples