D. Graph Gametime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputIn computer science, there is a method called "Divide And Conquer By Node" to solve some hard problems about paths on a tree. Let's desribe how this method works by function:solve(t) (t is a tree):   Chose a node x (it's common to chose weight-center) in tree t. Let's call this step "Line A".  Deal with all paths that pass x.  Then delete x from tree t.  After that t becomes some subtrees.  Apply solve on each subtree. This ends when t has only one node because after deleting it, there's nothing. Now, WJMZBMR has mistakenly believed that it's ok to chose any node in "Line A". So he'll chose a node at random. To make the situation worse, he thinks a "tree" should have the same number of edges and nodes! So this procedure becomes like that.Let's define the variable totalCost. Initially the value of totalCost equal to 0. So, solve(t) (now t is a graph):   totalCost = totalCost + (size of t). The operation "=" means assignment. (Size of t) means the number of nodes in t.  Choose a node x in graph t at random (uniformly among all nodes of t).  Then delete x from graph t.  After that t becomes some connected components.  Apply solve on each component. He'll apply solve on a connected graph with n nodes and n edges. He thinks it will work quickly, but it's very slow. So he wants to know the expectation of totalCost of this procedure. Can you help him?InputThe first line contains an integer n (3 ≤ n ≤ 3000) — the number of nodes and edges in the graph. Each of the next n lines contains two space-separated integers ai, bi (0 ≤ ai, bi ≤ n - 1) indicating an edge between nodes ai and bi.Consider that the graph nodes are numbered from 0 to (n - 1). It's guaranteed that there are no self-loops, no multiple edges in that graph. It's guaranteed that the graph is connected.OutputPrint a single real number — the expectation of totalCost. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.ExamplesInput53 42 32 40 41 2Output13.166666666666666Input30 11 20 2Output6.000000000000000Input50 11 22 03 04 1Output13.166666666666666NoteConsider the second example. No matter what we choose first, the totalCost will always be 3 + 2 + 1 = 6.
Input53 42 32 40 41 2
Output13.166666666666666
['graphs', '*3000']