Absurdistan Roads II

Photo by Ivan
McClellan

The people of Absurdistan discovered how to build roads only last year. After the discovery, each city decided to build its own road, connecting the city with some other city. Each newly built road can be used in both directions.

Absurdistan is full of absurd coincidences. It took all
$N$ cities precisely one
year to build their roads. And even more surprisingly, when the
roads were finished it was possible to travel from every city
to any other city using the newly built roads. We say that such
a road network is *connected*. Being interested in
mathematics and probability, you started wondering how unlikely
this coincidence really is.

Each city picked uniformly at random another city to which they built a road. Calculate the probability that the road network ends up being connected.

The first line contains an integer $N$ $(2\le N\le 140)$ – the number of cities.

Output one line containing a floating point number denoting the probability that the randomly built road network with $N$ cities and $N$ roads is connected. Your answer should have an absolute error of at most $10^{-8}$.

Sample Input 1 | Sample Output 1 |
---|---|

4 |
0.962962962963 |

Sample Input 2 | Sample Output 2 |
---|---|

2 |
1.000000000000 |