Cactus Determinant

A cactus graph is a simple connected undirected graph in which each edge belongs to at most one simple cycle.

The adjacency matrix of an $N$-vertex graph is an $N \times N$ integer matrix where $A_{i,j}$ is $1$ if there is an edge between vertices $i$ and $j$, and $0$ otherwise.

The determinant of an $N \times N$ matrix is defined as

$\sum_{p \in P(N)}(-1)^{inv(p)}\left(\prod_{i=1}^{N}A_{i,p_i}\right)$

where $P(N)$ is the set of all permutations of size $N$, and $inv(p)$ is the number of pairs $1 \le i < j \le N$ such that $p_i > p_j$.

993244853 is a prime number that looks like $998244353 = 119 \times 2^{23} + 1$, but is actually not.

Find the determinant of the adjacency matrix of the given cactus graph, modulo 993244853.

The first line contains $N$ and $M$, the number of vertices and edges of the cactus graph. ($1 \le N \le 50000$, $0 \le M \le 250000$)

Each of the next $M$ lines contains two distinct integers $s$ and $e$, the endpoints of an edge. ($1 \le s, e \le N$, $s \neq e$)

The graph is connected, has no loops or multiple edges, and each edge belongs to at most one simple cycle.

Print the determinant of the adjacency matrix of the given cactus graph, modulo 993244853.