405100: GYM101790 J Distress signal

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Distress signaltime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

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

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

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

Output

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

ExamplesInput
4
1 2
1 3
3 4
3
1 2
1 3
Output
0.166666666667
Input
2
1 2
3
1 2
1 3
Output
0.000000000000

加入题单

上一题 下一题 算法标签: