405100: GYM101790 J Distress signal

The country of Doubland consists of two archipelagos, including N and M islands.

The islands inside the archipelagoes are connected by N - 1 and M - 1 bridges respectively.

It is possible to move on the bridges in both directions. Also it is possible to reach every island from every island of the archipelago, moving only on bridges. The time spent on the road will be equal to the number of bridges passed.

Doubland is a poor country. Therefore, when there is a threat of a major natural disaster, the government can only turn on alarming sirens simultaneously on all islands and hope that some of the residents will get a distress signal to the mainland.

The most reliable way to signal is the telegraph. Unfortunately, telegraphs have survived only on islands that are connected to their archipelago by exactly one bridge, and on each of the archipelagos only one Morse code specialist resides.

Determing the expect value of the minimum time, when at least one of the Morse code specialists reachs the telegraph, provided that each of them at the moment of triggering alarm sirens can be equally likely to be on any of the islands of its archipelago.

The first line contains one integer N (2 ≤ N ≤ 10⁵), detonig the number of islands of the first archipelago.

The next line contains N - 1 lines that contain two integers X_i and Y_i (1 ≤ X_i, Y_i ≤ N), denoting the i-th bridge connects islands X_i and Y_i of the first archipelago.

The next line contains one integer M (2 ≤ M ≤ 10⁵), detonig the number of islands of the second archipelago.

The next line contains M - 1 lines that contain two integers U_j, V_j (1 ≤ U_j, V_j ≤ M), denoting the j-th bridge connects islands U_j and V_j of the second archipelago.

Display one real number: the expect value. The answer is correct if the absolute or relative error does not exceed 10^- 9.

4
1 2
1 3
3 4
3
1 2
1 3

0.166666666667

2
1 2
3
1 2
1 3

0.000000000000