Convex Sets on Graph

Time limit2sMemory limit512 MB

Summary

Count the vertex subsets S of a connected graph where every simple path between two vertices of S lies entirely inside S, modulo 998244353.

Level: Hard9 of 10
Topics: Graph, Dynamic programming, Tree
Solved: No attempts yet

Problem

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. Count the convex subsets of vertices of a given graph.

Input

The first line 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. Each of the next $m$ lines contains two space-separated integers $x$ and $y$ , the endpoints of an edge ( $1 \leq x, y \leq n$ ; $x \neq y$ ). The graph is connected and has no multiple edges.

Output

Print the number of convex subsets modulo the prime $998\,244\,353$ .

Examples2

Example 1
Input
```
3 2
1 2
2 3
```
Expected output
```
7
```
Example 2
Input
```
3 3
1 2
2 3
3 1
```
Expected output
```
5
```