Consider the following problems:

FULL CYCLE SEARCH VERSION (FCS): Input: Graph G = (V, E) Output: A cycle that goes through all the nodes of G exactly once.

FULL CYCLE DECISION VERSION (FCD): Input: Graph G = (V, E) Output: If G has cycle that goes through all the nodes of G exactly once return YES, otherwise NO.

FULL PATH DECISION VERSION (FPD): Input: Graph G = (V, E) and two nodes s and t. Output: If G has a path from s to t that goes through all the nodes of G exactly once return YES, otherwise NO.

a) Show that FCS reduces to FCD.

b) Show that FPD reduces to FCD.

c) Show that FCD reduces to FPD.