405975: GYM102201 C Cactus Determinant

Memory Limit:1024 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Cactus Determinanttime limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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$$$.

Input

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.

Output

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

ExamplesInput
6 6
2 3
5 6
2 5
1 2
3 4
6 2
Output
993244852
Input
1 0
Output
0
Input
10 11
1 2
3 4
1 3
5 6
7 8
9 10
7 9
6 8
1 9
10 5
4 9
Output
993244849

加入题单

上一题 下一题 算法标签: