#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/8/problems/f

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/8/problems/f

Repovive

Graph Tiling - Repovive Standard Round 3 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

8F. Graph Tiling

3000 ptstype :zen to enter zen mode

by Hamza Hassanain

Time: 5sMemory: 512 MB

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

A tiling of the graph is a way to cover every vertex with tiles of two types:

A 1-node tile covers a single vertex.
A 2-node tile covers two distinct vertices that are connected by an edge.

Each vertex must be covered by exactly one tile. Count the number of distinct tilings modulo $998244353$ .

Constraints

$1 \le n \le 200\,000$
$n-1 \le m \le n-1+20$
The graph is simple, connected, and undirected
Answer modulo $998\,244\,353$

Input

$n \quad m$

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

Output

$ans$

Samples

Input

Explanation

The $4$ vertices form a star: vertex $1$ (center) is connected to vertices $2$ , $3$ , and $4$ (leaves).

If the center is a singleton: all three leaves must also be singletons. This gives $1$ tiling: $\{1\},\{2\},\{3\},\{4\}$ .

If the center is paired with a leaf: there are $3$ choices of which leaf to pair with via a $2$ -node tile. The remaining two leaves are singletons. This gives $3$ tilings: $\{1,2\},\{3\},\{4\}$ ; $\{1,3\},\{2\},\{4\}$ ; $\{1,4\},\{2\},\{3\}$ .

Total: $1 + 3 = 4$ .

Output

Input

Explanation

The graph is a $4$ -cycle: vertices $1$ – $2$ – $3$ – $4$ – $1$ . List all matchings:

No edge tiles (all singletons): $\{1\},\{2\},\{3\},\{4\}$ — $1$ tiling
One $2$ -node tile ( $4$ choices of edge): $\{1,2\},\{3\},\{4\}$ ; $\{2,3\},\{1\},\{4\}$ ; $\{3,4\},\{1\},\{2\}$ ; $\{4,1\},\{2\},\{3\}$ — $4$ tilings
Two disjoint $2$ -node tiles ( $2$ choices): $\{1,2\},\{3,4\}$ ; $\{4,1\},\{2,3\}$ — $2$ tilings

Total: $1 + 4 + 2 = 7$ .

Output

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

A tiling of the graph is a way to cover every vertex with tiles of two types:

A 1-node tile covers a single vertex.
A 2-node tile covers two distinct vertices that are connected by an edge.

Each vertex must be covered by exactly one tile. Count the number of distinct tilings modulo $998244353$ .

$1 \le n \le 200\,000$
$n-1 \le m \le n-1+20$
The graph is simple, connected, and undirected
Answer modulo $998\,244\,353$

$n \quad m$

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

$ans$

The $4$ vertices form a star: vertex $1$ (center) is connected to vertices $2$ , $3$ , and $4$ (leaves).

If the center is a singleton: all three leaves must also be singletons. This gives $1$ tiling: $\{1\},\{2\},\{3\},\{4\}$ .

Total: $1 + 3 = 4$ .

The graph is a $4$ -cycle: vertices $1$ – $2$ – $3$ – $4$ – $1$ . List all matchings:

No edge tiles (all singletons): $\{1\},\{2\},\{3\},\{4\}$ — $1$ tiling
One $2$ -node tile ( $4$ choices of edge): $\{1,2\},\{3\},\{4\}$ ; $\{2,3\},\{1\},\{4\}$ ; $\{3,4\},\{1\},\{2\}$ ; $\{4,1\},\{2\},\{3\}$ — $4$ tilings
Two disjoint $2$ -node tiles ( $2$ choices): $\{1,2\},\{3,4\}$ ; $\{4,1\},\{2,3\}$ — $2$ tilings

Total: $1 + 4 + 2 = 7$ .