Trees and Primes

Time limit2sMemory limit512 MB

Summary

Given a tree on N vertices, find the probability that a uniformly random pair of distinct vertices has a prime distance.

Level: Medium7 of 10
Topics: Tree, DFS, Number theory, Divide and conquer
Solved: No attempts yet

Problem

You are given a tree with $N$ vertices, numbered 1 through $N$ . The distance between two vertices is the number of edges on the path that joins them.

Two distinct vertices are chosen uniformly at random, so each of the $\binom{N}{2}$ unordered pairs is equally likely. Write a program that computes the probability that the distance between the two chosen vertices is a prime number.

Input

The first line contains the number of vertices $N$ ( $2 \le N \le 50000$ ).

Each of the next $N-1$ lines contains the numbers $u$ and $v$ of two vertices joined by an edge, separated by a space ( $1 \le u, v \le N$ , $u \ne v$ ).

The given graph is always a tree.

Output

Print the probability that the distance between the two chosen vertices is prime, with exactly 10 digits after the decimal point. Round half up at the eleventh digit and keep the trailing zeros. For example, if the probability is exactly $\frac{1}{2}$ , print 0.5000000000.

Examples5

Example 1
Input
```
5
1 2
2 3
3 4
4 5
```
Expected output
```
0.5000000000
```
Example 2
Input
```
2
1 2
```
Expected output
```
0.0000000000
```
Example 3
Input
```
3
1 2
2 3
```
Expected output
```
0.3333333333
```
Example 4
Input
```
5
1 2
1 3
1 4
1 5
```
Expected output
```
0.6000000000
```

Example 5

Input

Expected output

0.6444444444