Absurdistan의 도로 II

촬영: Ivan McClellan

Absurdistan 사람들은 불과 작년에 도로 건설 방법을 발견했다. 이 발견 이후 각 도시는 다른 도시 하나와 연결되는 자체 도로를 건설하기로 했다. 새로 건설된 각 도로는 양방향으로 이용할 수 있다.

Absurdistan에는 터무니없는 우연이 가득하다. $N$개의 모든 도시가 도로를 건설하는 데 정확히 일 년이 걸렸다. 더욱 놀랍게도 도로가 완공되자 새로 건설된 도로를 이용해 모든 도시에서 어떤 다른 도시로든 이동할 수 있었다. 이러한 도로망을 연결되어 있다고 한다. 수학과 확률에 관심이 있던 당신은 이 우연이 실제로 얼마나 일어나기 어려운지 궁금해졌다.

과제

각 도시는 균등한 확률로 다른 도시 하나를 선택하여 그 도시까지 도로를 건설했다. 도로망이 최종적으로 연결될 확률을 계산한다.

첫 줄에 도시의 수를 나타내는 정수 $N$ $(2\le N\le 140)$가 주어진다 -- 도시의 수이다.

$N$개의 도시와 $N$개의 도로로 무작위로 건설된 도로망이 연결될 확률을 나타내는 부동소수점 수 하나를 한 줄에 출력한다. 답의 절대 오차는 최대 $10^{-8}$여야 한다.