Hamiltonian cycle, verifying and finding
Let $P$ be an arbitrary simple path in the graph. If $P$ appears in a Hamiltonian cycle of the graph, you can remove all the vertices of $p$ except the first and the last vertex, connect these two vertices with an edge and the resulting graph must be Hamiltonian.

Keeping this in mind, we can build the Hamiltonian cycle step by step starting with path of length one, since you already described how to build such a path. Then we can extend a path of length $i$ to a path of length $i+1$ using the trick above, where we try all neighbors of the last vertex in the path as a next vertex and we apply the trick above to check if a Hamiltonian cycle exists where the new path is a part of the cycle. Note that we call the black-box at most $m := |E|$ times. Once we reach a path of length $n-3$ it is easy to complete the path into a Hamiltonian cycle in linear time.