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.

제한

힌트