그래프의 볼록 집합

시간 제한2초메모리 제한512 MB

요약

연결된 무방향 그래프에서 두 정점을 잇는 모든 단순 경로가 부분집합 안에 머무는 정점 집합의 개수를 998244353으로 나눈 나머지로 구합니다.

난이도: 어려움10점 중 9점
유형: 그래프, 동적 계획법, 트리
정답자: 아직 제출이 없습니다

문제

무방향 그래프의 정점 집합 $S$ 에 대해, $S$ 에 속한 서로 다른 두 정점 사이의 임의의 단순 경로가 모두 $S$ 안에 놓이면 $S$ 를 볼록(convex)하다고 한다. 주어진 그래프에서 볼록한 정점 집합의 개수를 구하라.

입력

첫 줄에 정점의 개수 $n$ 과 간선의 개수 $m$ 이 주어진다 ( $1 \leq n \leq 3 \cdot 10^5$ ; $n - 1 \leq m \leq 3 \cdot 10^5$ ). 이어지는 $m$ 개의 줄에는 각 간선의 두 끝점 $x$ 와 $y$ 가 공백으로 구분되어 주어진다 ( $1 \leq x, y \leq n$ ; $x \neq y$ ). 그래프는 연결되어 있고 다중 간선은 없다.

출력

볼록한 정점 집합의 개수를 소수 $998\,244\,353$ 으로 나눈 나머지를 출력한다.

예제2

예제 1
입력
```
3 2
1 2
2 3
```
예상 출력
```
7
```
예제 2
입력
```
3 3
1 2
2 3
3 1
```
예상 출력
```
5
```