The Longest Path problem takes a graph G and an integer K and asks if there exists a path in G of at least Kedges such that no vertex or edge repeats on the path. The Hamiltonian Cycle problem takes a graph G and asks if there exists a path in G that starts at some vertex, visits every vertex on G and returns to the starting vertex visiting each vertex exactly once and never repeating an edge. Give an efficient reduction of the Hamiltonian Cycle problem to the Longest Path problem. Give the running time of the reduction, and prove the reduction is correct.