Meyniel's theorem + finding a Hamiltonian path for a specific graph family
It is enough to prove your claim for the case of a tournament, in which for every pair of vertices $v\neq w$, exactly one of the edges $(v,w),(w,v)$ is in the graph. Wikipedia has an algorithmic proof that every such graph has a Hamiltonian path. If the tournament is strongly connected, it has a Hamiltonian cycle.