  We estimate the minimum number of distance queries that is sufficient to
reconstruct the binomial random graph $G(n,p)$ with constant diameter with high
probability. We get a tight (up to a constant factor) answer for all
$p>n^{-1+o(1)}$ outside "threshold windows" around $n^{-k/(k+1)+o(1)}$,
$k\in\mathbb{Z}_{>0}$: with high probability the query complexity equals
$\Theta(n^{4-d}p^{2-d})$, where $d$ is the diameter of the random graph. This
demonstrates the following non-monotone behaviour: the query complexity jumps
down at moments when the diameter gets larger; yet, between these moments the
query complexity grows. We also show that there exists a non-adaptive algorithm
that reconstructs the random graph with $O(n^{4-d}p^{2-d}\ln n)$ distance
queries with high probability, and this is best possible.
