Consider an undirected, unweighted graph G = (V. E). A Hamiltonian Cycle is a cycle in G that visits each vertex exactly once. (Recall that an Eulerian Cycle was a cycle that visited each edge exactly once.) A Hamiltonian Path from a vertex s eV to a vertexte V is a path from s to t which visits each vertex exactly once. Define the decision) problems HAM-CYCLE and HAM-PATH in the obvious way as follows: HAM-CYCLE: Given an undirected graph G = (V, E), does have a Hamiltonian cycle? HAM-PATH: Given an undirected graph G = (V, E), does G have a Hamiltonian path? We will consider the size of any instance of these problems to be n = |V], the number of vertices. (a) Explain why both of these decision) problems are in NP. (b) Show that HAM-PATH S, HAM-CYCLE. That is, show how to transform any instance of the HAM-PATH problem into an instance of the HAM-CYCLE problem, where r solves the HAM-PATH problem if and only if x' solves the HAM-CYCLE problem. HAM-CYCLE: (c) Circle the leter of the most appropriate interpretation of the statement HAM-PATH S A. HAM-PATH is as easy or easier than HAM-CYCLE. B. HAM-PATH is as hard or harder than HAM-CYCLE. C. HAM-PATH is strictly easier than HAM-CYCLE. D. HAM-PATH is strictly harder than HAM-CYCLE