Làng X có ~N~ khu dân cư được nối với nhau bởi ~N-1~ con đường, sao cho tồn tại đường đi giữa 2 khu dân cư bất kỳ. Để đáp ứng nhu cầu cấp điện cho các hộ dân, chính quyền muốn xây 2 trạm biến áp tại 2 trong số ~N~ khu dân cư này. Vì lý do phong thủy, họ muốn chọn 2 khu dân cư sao cho khoảng cách giữa chúng (số con đường trên đường đi ngắn nhất) là một số nguyên tố.

Hãy giúp chính quyền biết, nếu chọn ngẫu nhiên 2 khu dân cư thì xác suất 2 khu dân cư này phù hợp để xây trạm biến áp là bao nhiêu?

Input

Dòng đầu tiên chứa 1 số nguyên dương ~N~ (~2 \le N \le 50000~).

~N-1~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương ~u~ và ~v~ (~1 \le u,v \le N~, ~u \neq v~) cho biết có con đường nối 2 khu dân cư ~u~ và ~v~.

Dữ liệu đầu vào đảm bảo tồn tại đường đi giữa 2 khu dân cư bất kỳ.

Output

In ra 1 số thực: xác suất chọn ra 2 khu dân cư phù hợp để xây trạm biến áp.

Scoring

Sample Input 1

5
1 2
2 3
3 4
4 5

Sample Output 1

0.500000000

Sample Input 2

8
4 8
2 7
1 6
3 5
8 3
2 5
4 6

Sample Output 2

0.535714286

Notes

Sample 1:

Có ~C^2_5 = 10~ cách chọn 2 khu dân cư.

Có ~5~ cặp khu dân cư phù hợp là: 1-3, 2-4, 3-5, 1-4, 2-5.

Vậy xác suất chọn ra 2 khu dân cư phù hợp là ~5 / 10 = 0.5.~