시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

A set of vertices of an undirected graph is convex if, for any two distinct vertices from the set, any simple path between them lies entirely within that set. Your task is to compute the number of convex subsets of vertices of a given graph.

입력

The first line of the input contains two integers $n$ and $m$ ($1 \leq n \leq 3 \cdot 10^5$; $n - 1 \leq m \leq 3 \cdot 10^5$): the number of vertices and the number of edges correspondingly. The $i$-th of the following $m$ lines contains two space-separated integers $x$ and $y$: the endpoints of the $i$-th edge ($1 \leq x, y \leq n$; $x \neq y$). It is guaranteed that the graph is connected and does not contain multiple edges.

출력

Print one number: the answer modulo prime number $998\,244\,353$.

예제 입력 1

3 2
1 2
2 3

예제 출력 1

7

예제 입력 2

3 3
1 2
2 3
3 1

예제 출력 2

5