Prove that the below decision problems is NP-Complete. You may use only the following NP-Complete problems in the polynomial-time reductions: Vertex Cover AND Hamiltonian Circuit (please use both; DO NOT use 3-SAT or copy other answers!!)

1. Longest Simple Cycle: Given a weighted, directed graph G, find whether or not there is a simple cycle of at least k vertices. (A simple cycle is a cycle where the only vertex that appears twice is the start/end.)