Background

Please note: This problem is not a template problem for tree decomposition.

Problem Description

Given a tree \( T \) with \( n \) nodes and \( m \) distinct paths \( I_i = (u_i, v_i) \) where \( u_i \neq v_i \). Specifically, \( I_i \) represents the set of all nodes on the simple path between \( u_i \) and \( v_i \) in the tree.

Consider a path \( I = (u, v) \) on \( T \). Define \( f(I) = \sum_{i=1}^m \sum_{j=1}^m [I_i \cup I = I_j \cup I] \).

For all distinct paths \( I \) on \( T \), find the sum of \( f(I) \) and output the answer modulo \( 998244353 \). That is, you need to compute \( \left( \sum_{u=1}^n \sum_{v=u+1}^n f((u, v)) \right) \bmod 998244353 \).

Input Format

The first line contains an integer \( S \), representing the subtask number. The subtask number for samples is \(-1\).

The second line contains two integers \( n \) and \( m \), representing the size of the tree and the number of paths, respectively.

The next \( n-1 \) lines each contain two integers \( x_i \) and \( y_i \), representing an edge in the tree.

The next \( m \) lines each contain two integers \( u_i \) and \( v_i \), representing the \( i \)-th path \( I_i \).

It is guaranteed that all given paths are distinct.

Output Format

Output a single integer representing the answer.

Sample Input and Output

Input Sample #1

-1
3 3
1 2
2 3
1 2
2 3
1 3

Output Sample #1

32

Input Sample #2

-1
4 6
1 2
1 3
1 4
1 2
1 3
1 4
2 3
2 4
3 4

Output Sample #2

120

Input Sample #3

-1
7 7
1 2
1 3
2 4
4 5
5 6
5 7
5 7
3 1
4 7
7 1
2 6
3 6
3 5

Output Sample #3

330

Notes/Hints

This problem uses bundled testing with a total of 25 subtasks, numbered from 0 to 24. Note that the actual subtask number for judging is the subtask number +1.

The remainder of the subtask number modulo 5 categorizes the subtasks by data size.

• If the subtask number modulo 5 is 0, then \( n, m \leq 100 \), denoted as A1.
• If the subtask number modulo 5 is 1, then \( n, m \leq 500 \), denoted as B1. Depends on A1.
• If the subtask number modulo 5 is 2, then \( n, m \leq 1557 \), denoted as C1. Depends on B1.
• If the subtask number modulo 5 is 3, then \( n, m \leq 85500 \), denoted as D1. Depends on C1.
• If the subtask number modulo 5 is 4, then \( n, m \leq 2 \times 10^5 \), denoted as E1. Depends on D1.

The quotient of the subtask number divided by 5 categorizes the subtasks by special restrictions.

• If the quotient is 0, then \( T \) is a chain, denoted as A2.
• If the quotient is 1, then \( T \) is a star, denoted as B2.
• If the quotient is 2, then all path endpoints are distinct, denoted as C2.
• If the quotient is 3, then all paths have the same endpoint, denoted as D2.
• If the quotient is 4, then there are no special restrictions, denoted as E2. Depends on A2, B2, C2, D2.

For 100% of the data, \( 2 \leq n \leq 2 \times 10^5 \), \( 1 \leq m \leq \min(\frac{n(n-1)}{2}, 2 \times 10^5) \), \( 1 \leq u_i, v_i, x_i, y_i \leq n \), and all \( (x_i, y_i) \) form a tree, all \( I_i = (u_i, v_i) \) are distinct, and \( u_i \neq v_i \).

The scores for each subtask are as follows:

Note: Luogu's judging system does not enforce subtask dependencies.

Source: 2022 Training Team Mutual Test Round 4.

Problem Author: Alex_Wei.

见题面 Input 部分

见题面 Output 部分