Adding Edges

You are given a tree $T$ with $N$ vertices and an undirected graph $G$ with $N$ vertices and $M$ edges. The vertices of each graph are numbered $1$ to $N$. The $i$\-th of the $N-1$ edges in $T$ connects Vertex $a_i$ and Vertex $b_i$, and the $j$\-th of the $M$ edges in $G$ connects Vertex $c_j$ and Vertex $d_j$. Consider adding edges to $G$ by repeatedly performing the following operation: * Choose three integers $a$, $b$ and $c$ such that $G$ has an edge connecting Vertex $a$ and $b$ and an edge connecting Vertex $b$ and $c$ but not an edge connecting Vertex $a$ and $c$. If there is a simple path in $T$ that contains all three of Vertex $a, b$ and $c$ in some order, add an edge in $G$ connecting Vertex $a$ and $c$. Print the number of edges in $G$ when no more edge can be added. It can be shown that this number does not depend on the choices made in the operation. ## Constraints * $2 \leq N \leq 2000$ * $1 \leq M \leq 2000$ * $1 \leq a_i, b_i \leq N$ * $a_i \neq b_i$ * $1 \leq c_j, d_j \leq N$ * $c_j \neq d_j$ * $G$ does not contain multiple edges. * $T$ is a tree. ## Input Input is given from Standard Input in the following format: $N$ $M$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$ $c_1$ $d_1$ $:$ $c_M$ $d_M$ [samples]