그래프의 행렬식

시간 제한1초메모리 제한256 MB

요약

연결된 그래프에서 간선 수가 정점 수보다 최대 50 많을 때, 인접 행렬의 행렬식을 998244353으로 나눈 나머지를 구합니다.

난이도: 어려움10점 중 8점
유형: 그래프, 트리, 행렬
정답자: 아직 제출이 없습니다

문제

연결된 무방향 그래프가 있다. 이 그래프에서는 간선 수와 정점 수의 차이가 $50$ 이하이다. 이 그래프의 인접 행렬의 행렬식을 $998\,244\,353$ 으로 나눈 나머지를 구하라.

입력

첫 번째 줄에 정점 수 $n$ 과 간선 수 $m$ 이 주어진다 ( $1 \le n \le 2 \cdot 10^{5}$ , $n - 1 \le m \le n + 50$ ). 다음 $m$ 개의 줄에는 각각 간선으로 연결된 두 정점 $u$ , $v$ 가 주어진다 ( $1 \le u, v \le n$ ). 그래프에는 자기 루프와 중복 간선이 없고, 그래프는 연결되어 있다.

출력

그래프 인접 행렬의 행렬식을 $998\,244\,353$ 으로 나눈 나머지를 한 줄에 출력한다.

예제4

예제 1
입력
```
4 3
1 2
2 3
3 4
```
예상 출력
```
1
```

예제 2

입력

예상 출력

예제 3
입력
```
1 0
```
예상 출력
```
0
```
예제 4
입력
```
2 1
2 1
```
예상 출력
```
998244352
```