Головоломка Хакерранка. Сколько ребер необходимо для того, чтобы случайный граф соединился

Это головоломка Interviewstreet:

У нас есть страна, содержащая N городов. Каждый день мы выбираем 2 города так, чтобы между ними не было дороги, и строим дорогу между ними. Мы выбираем каждую пару несмежных городов с равной вероятностью. Пусть X — количество дней до получения подключенной страны. Каково ожидаемое значение X? Вывод целочисленной части ответа.

На самом деле они спрашивают, какое количество рёбер m необходимо (в среднем) для соединения случайного графа G(n, m).

Написав программу, которая фактически выполнила эксперимент, я придумал это «решение», которое проходит тесты 9/10

$f = fopen('php://stdin', 'r');
$n = intval(fgets($f));
echo round(1.25 * $n * log($n, 10));

Так можно ли его решить с помощью одной формулы? Как правильно найти вероятность связности случайного графа?