Problem G
Absurdistan Roads II
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.
Task
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.
Input
The first line contains an integer $N$ $(2\le N\le 140)$ – the number of cities.
Output
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 |
