Counting Independent Sets of Tree Paths

Given an unrooted tree with \(n\) nodes and \(n-1\) edges, and \(m\) specified paths on the tree, count the number of independent set schemes that can be formed by these paths. A set of paths is called an independent set if no two paths in the set share any common vertex on the tree. Note that the empty set and any set containing a single path are also considered independent sets. Since the answer may be extremely large, output it modulo \(998,244,353\).

Definition: A path \(P\) between two nodes in a tree is the unique simple sequence of vertices connecting them. Two paths \(P_1\) and \(P_2\) are said to intersect if they share at least one common vertex. An independent set of paths is a subset of the \(m\) given paths such that no two chosen paths intersect.

inputFormat

The input is given in the following format:

 n m
 u1 v1
 u2 v2
 ... (n-1 lines for tree edges)
 a1 b1
 a2 b2
 ... (m lines for paths, each given by two endpoints)

Here, the tree is undirected and connected.

outputFormat

Output a single integer: the number of independent sets (subsets of the \(m\) paths with no pair of intersecting paths) modulo \(998,244,353\).

sample

3 2
1 2
2 3
1 2
2 3

3