Cascade Centrality

무방향 그래프 $G=(V,E)$에서 정점 $i$의 캐스케이드 중심성은 다음과 같이 정의한다. $1 + \sum_{j \in V \setminus \{i\}} \sum_{P \in P_{ij}} \frac{1}{\chi_P}$ 여기서 $P_{ij}$는 정점 $i$에서 정점 $j$까지 가는 모든 단순 경로의 집합이다. 경로 $P$의 차수 곱 $\chi_P$는 경로 위의 모든 정점의 차수를 곱한 값이며, 끝 정점은 포함하고 시작 정점은 제외한다.

$G$는 트리이므로 $P_{ij}$에는 경로가 항상 하나만 있다. $G$에 있는 모든 정점의 캐스케이드 중심성의 평균을 구하라.

첫째 줄에 트리의 정점 개수 $N$ $(1 \leq N \leq 100)$이 주어진다. 이후 $N-1$개의 줄에 정점 $u_i$와 $v_i$ $(1 \leq u_i, v_i \leq N)$를 잇는 무방향 간선이 공백으로 구분된 두 정수로 주어진다. 자기 자신과 잇는 간선은 없으며, 두 정점 사이의 간선은 최대 하나이다. 주어지는 그래프는 연결되어 있고 사이클이 없다.

그래프에 있는 모든 정점의 캐스케이드 중심성의 평균을 출력한다. 정답과 상대 오차 또는 절대 오차가 $10^{-6}$ 이하이면 맞은 것으로 본다.