Connected Subgraph

Time limit1sMemory limit256 MB

Summary

Count the ways to delete some edges from a tree plus k extra edges so the remaining graph stays connected, modulo 998244353.

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

Problem

Rikka draws a tree with $n$ vertices labeled $1, 2, \ldots, n$ and adds $k$ extra edges to it. Count the ways she can remove zero or more edges so that the remaining graph stays connected, modulo $998\,244\,353$ .

Input

The first line contains two integers $n$ and $k$ ( $1 \le n \le 10^5$ , $0 \le k \le 10$ ). Each of the next $n-1$ lines contains two integers $a_i$ and $b_i$ , a tree edge between vertices $a_i$ and $b_i$ ( $1 \le a_i, b_i \le n$ ). Each of the last $k$ lines contains two integers $u_i$ and $v_i$ , an extra edge between vertices $u_i$ and $v_i$ ( $1 \le u_i, v_i \le n$ ). The tree edges form a tree. The resulting graph has no self-loops and no parallel edges.

Output

Print one integer: the number of ways to remove zero or more edges so that the graph remains connected, modulo $998\,244\,353$ .

Examples2

Example 1
Input
```
5 1
1 2
2 3
3 4
4 5
1 5
```
Expected output
```
6
```
Example 2
Input
```
4 2
1 2
2 3
2 4
3 4
1 4
```
Expected output
```
14
```