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

문제

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

입력

The first line contains two integers $n$ and $k$ ($1 \leq n \leq 10^5$, $0 \leq k \leq 10$). 

The $i$-th of the following $(n - 1)$ lines contains two integers $a_i$ and $b_i$, which denotes a tree edge between vertices $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq n$). It is guaranteed that these edges form a tree.

The $i$-th of the last $k$ lines contains two integers $u_i$ and $v_i$, which denote an extra edge between vertices $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$). It is guaranteed that the resulting graph has no self-loops and no parallel edges.

출력

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

예제 입력 1

5 1
1 2
2 3
3 4
4 5
1 5

예제 출력 1

6

예제 입력 2

4 2
1 2
2 3
2 4
3 4
1 4

예제 출력 2

14