Defeating Dark by Severing Its Chains

Dark is a legendary force represented by an undirected graph with N nodes. The graph has two types of edges:

• Primary edges: There are exactly N-1 primary edges, and they form a tree (i.e. there is a unique path between any two nodes using only primary edges).
• Additional edges: There are M additional edges.

You have the ability to defeat Dark by splitting it into two disconnected parts. Initially, the additional edges are invincible so you can only remove one primary edge. Once you remove a primary edge, Dark enters a defensive mode: the primary edges become invincible and one additional edge can be removed.

Even if the removal of the primary edge immediately disconnects Dark, you must also remove one additional edge for the defeat to count.

Your task is to count the number of valid strategies to defeat Dark. A strategy is defined by choosing:

1. One primary edge to remove.
2. Then one additional edge to remove.

For a given primary edge removal, let its removal split the tree into two components A and B. Consider an additional edge that connects a node in A and a node in B as a bridging additional edge for that particular primary edge.

The result after both removals must be that Dark is disconnected. In other words, if the primary edge removal yields a situation where there are no bridging additional edges (i.e. no additional edge connects the two resulting subtrees), then any removal of an additional edge (even one in the same component) still leaves Dark disconnected. However, if there is exactly one bridging additional edge, then you must remove that particular additional edge; if there are more than one bridging additional edges, then no additional edge removal will disconnect the graph because at least one bridging edge will remain.

Formally, for each primary edge e which, when removed, partitions the nodes into a subtree S (attached to the child in the DFS tree) and its complement, define x as the number of additional edges with exactly one endpoint in S. The number of valid choices for that primary edge is:

• If x = 0: M (any additional edge removal works).
• If x = 1: 1 (you must remove the unique bridging edge).
• If x ≥ 2: 0 (the graph will remain connected).

Your answer is the sum over all primary edges of the valid number of additional edge removals.

The conditions in mathematical notation:

• For a primary edge e connecting parent p and child c, let the subtree S be the set of nodes with indices satisfying $$ tin[c] \le tin[u] < tout[c] $$ for any node u in S (obtained via a DFS).
• For an additional edge \((u,v)\), it contributes to the count for e if and only if $$ \big( tin[c] \le tin[u] < tout[c] \big) \oplus \big( tin[c] \le tin[v] < tout[c] \big)=1. $$

Calculate and print the total number of valid strategies.

inputFormat

The first line contains two integers N and M (N ≥ 2).

The next N-1 lines each contain two integers u and v representing a primary edge.

The following M lines each contain two integers u and v representing an additional edge.

outputFormat

Output a single integer, the total number of valid strategies to defeat Dark.

sample

3 1
1 2
2 3
1 3

2