Score : 2200 points
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:
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.
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
Print the final number of edges in G.
5 3 1 2 1 3 3 4 1 5 5 4 2 5 1 5
6
We can have at most six edges in G by adding edges as follows:
7 5 1 5 1 4 1 7 1 2 2 6 6 3 2 5 1 3 1 6 4 6 4 7
11
13 11 6 13 1 2 5 1 8 4 9 7 12 2 10 11 1 9 13 7 13 11 8 10 3 8 4 13 8 12 4 7 2 3 5 11 1 4 2 11 8 10 3 5 6 9 4 10
27