시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.4 초 1024 MB 17 9 7 53.846%

## 문제

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.

## 예제 입력 1

6 6
2 3
5 6
2 5
1 2
3 4
6 2


## 예제 출력 1

993244852


## 예제 입력 2

1 0


## 예제 출력 2

0


## 예제 입력 3

10 11
1 2
3 4
1 3
5 6
7 8
9 10
7 9
6 8
1 9
10 5
4 9


## 예제 출력 3

993244849