17460번 - Cactus Determinant 다국어

A Cactus graph is a simple connected undirected graph where each edge lies in at most one simple cycle.

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

The Determinant of a $N\times N$ matrix is defined as $\sum_{p \in P(N)}{(-1)^{inv(p)}(\prod_{i=1}^{n}{A_{i, p_i}})}$ , 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.

This problem asks you to calculate the determinant of an adjacency matrix of given cactus graph mod $993244853$.

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

In the next $M$ lines, two distinct integers $s, e$ denoting each endpoint of the edges are given. ($1 \le s, e \le N, s \neq e$).

It is guaranteed that the graph is connected, it does not contain loops or multiple edges, and every edge belongs to at most one simple cycle. 

Print the determinant of an adjacency matrix of given cactus graph mod 993244853.