The HAMILTONIAN CYCLE problem asks if an input graph G with n vertices contains as a subgraph the cycle graph with n vertices. The HAMILTONIAN PATH problem asks if an input graph G with n vertices contains as a subgraph the path graph with n vertices. (i) Show that HAMILTONIAN CYCLE belongs to the class NP. (ii) Show a reduction of the HAMILTONIAN CYCLE problem to the HAMILTONIAN PATH problem.