Yuki is a clever girl and she firmly believes that \(NP\neq P\).
One day TruthBoy, a friend of Yuki, claims that he has found a polynomial-time algorithm to solve Hamiltonian cycle problem, a famous NP-Complete problem.
There is a graph \(G=(V,E)\) with \(n\) nodes and \(m\) edges. Each road is unidirectional, that is an edge from \(u\) to \(v\) cannot be passed from \(v\) to \(u\). Let node \(1\) be the capital. The path starting at the capital node, visiting every non-capital node exactly once, and finishing in the capital is called a Hamiltonian cycle. And to determine the existence of Hamiltonian cycles in a given graph is called the Hamiltonian cycle problem.
Yuki does not think that TruthBoy has really solved the problem. However, TruthBoy can always give the correct answers to Yuki’s tests. To know the truth, Yuki turns to you for help. Can you help her to find out how TruthBoy solves the problem?