카투스 그래프의 행렬식

카투스 그래프(Cactus graph)는 연결된 단순 무방향 그래프이며, 각 간선이 많아야 하나의 단순 사이클에 속하는 그래프이다.

$N$개의 정점을 가진 그래프의 인접 행렬은 $N \times N$ 정수 행렬이다. 정점 $i$와 $j$ 사이에 간선이 있으면 $A_{i,j}$는 $1$, 없으면 $0$이다.

$N \times N$ 행렬의 행렬식은 다음과 같이 정의한다.

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

여기서 $P(N)$은 크기 $N$인 모든 순열의 집합이고, $inv(p)$는 $p_i > p_j$를 만족하는 $1 \le i < j \le N$인 쌍의 개수이다.

993244853은 소수이며, $998244353 = 119 \times 2^{23} + 1$과 비슷한 모양이지만 실제로는 그 형태가 아니다.

주어진 카투스 그래프의 인접 행렬의 행렬식을 993244853으로 나눈 나머지를 구하라.

첫 줄에 카투스 그래프의 정점 개수 $N$과 간선 개수 $M$이 주어진다. ($1 \le N \le 50000$, $0 \le M \le 250000$)

다음 $M$개의 줄에는 간선의 양 끝점 $s$, $e$가 주어진다. ($1 \le s, e \le N$, $s \neq e$)

그래프는 연결되어 있고, 자기 루프와 중복 간선이 없으며, 각 간선은 많아야 하나의 단순 사이클에 속한다.

주어진 카투스 그래프의 인접 행렬의 행렬식을 993244853으로 나눈 나머지를 출력한다.