Minimum Spanning Tree on Pair Graph of a Rooted Tree

You are given a rooted tree with \(n\) vertices and \(n-1\) directed edges. In addition, there are \(m\) pairs \((x_i, y_i)\) (\(1 \le i \le m\)), where each \(x_i\) and \(y_i\) is a vertex of the tree.

For any two vertices \(a\) and \(b\) in the tree, define the function \(D(a,b)\) as the number of vertices that are in the subtree of \(a\) (when \(a\) is considered as the root of its subtree) but not in the subtree of \(b\) (when \(b\) is the root). In other words, \[ D(a,b)=\begin{cases} \text{size}(a)-\text{size}(b) & \text{if } b \text{ is in the subtree of } a,\\ \text{size}(a) & \text{otherwise.} \end{cases} \] Note that when \(a=b\), \(D(a,b)=0\).

Now, consider a complete graph whose vertices correspond to the given \(m\) pairs. The weight of the edge connecting pair \(i\) and pair \(j\) is defined as: \[ W(i,j)=D(x_i,x_j)+D(x_j,x_i)+D(y_i,y_j)+D(y_j,y_i). \]

Your task is to compute the total weight of the minimum spanning tree (MST) of this complete graph.

Note: You may assume that the tree is rooted at vertex 1 and the vertices are numbered from 1 to \(n\).

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, representing the number of vertices in the tree and the number of pairs respectively.

The next \(n-1\) lines each contain two integers \(u\) and \(v\), denoting there is an edge from vertex \(u\) to vertex \(v\) in the rooted tree (i.e. \(u\) is the parent of \(v\)).

The following \(m\) lines each contain two integers \(x_i\) and \(y_i\) representing the \(i\)th pair.

outputFormat

Output a single integer representing the total weight of the minimum spanning tree of the complete graph formed by the given pairs.

sample

3 2
1 2
1 3
1 2
1 3

2