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?