Tree Paths Union Summation

You are given a tree \(T\) with \(n\) nodes and \(m\) distinct paths \(I_i=(u_i,v_i)\) on the tree (with \(u_i \neq v_i\)). For each given path \(I_i\), let the set of nodes on the simple path between \(u_i\) and \(v_i\) be denoted by \(I_i\) as well.

For any path \(I=(u,v)\) on \(T\) (here, note that a path \(I=(u,v)\) is defined as the unique simple path between \(u\) and \(v\); when \(u=v\), it is the trivial path containing only one node), define \[ f(I)=\sum_{i=1}^{m}\sum_{j=1}^{m} \Bigl[ I_i\cup I = I_j\cup I \Bigr], \] where \([P]\) equals \(1\) if proposition \(P\) is true and \(0\) otherwise.

Your task is to compute the sum of \(f(I)\) over all different paths \(I\) on \(T\) (that is, over all pairs \((u,v)\) with \(1\le u\le v\le n\)) modulo \(998244353\). In other words, you need to compute \[ \left( \sum_{u=1}^{n}\sum_{v=u}^{n} f((u,v)) \right) \bmod 998244353. \]

Note: The union \(I_i \cup I\) is taken as the set union of nodes in the two paths.

inputFormat

The first line contains two integers \(n\) and \(m\) \((1\leq n\leq 100,\, 0\le m\le \min(\text{number of possible paths in } T, 100))\), representing the number of nodes in the tree and the number of given paths respectively.

The next \(n-1\) lines each contain two integers \(u\) and \(v\) representing an edge in the tree \(T\).

The following \(m\) lines each contain two integers \(u_i\) and \(v_i\) \((u_i\neq v_i)\) defining a given path on the tree. It is guaranteed that these \(m\) paths are distinct.

outputFormat

Output a single integer denoting the sum of \(f(I)\) over all paths \(I=(u,v)\) (with \(1\le u\le v\le n\)) modulo \(998244353\).

sample

3 1
1 2
2 3
1 3

6