Disclaimer: It's possible that I've misunderstood something in the statement because I don't speak Vietnamese, I just copy pasted it into Google translate.

I have a feeling this task requires heuristics for the following reasons:

1. Extremely low AC rate and from looking at submission list, most AC submissions are from problem author (author name is on the right on problem statement).
2. Users that got AC also had several TLE submissions hovering around the AC range (in the 30s), which would be unlikely if there was a provable polynomial time solution.
3. In the comment section, there's a comment from author that seems to roughly translate to "greedy", which is just flat out wrong.

Doing some Googling, there are a number of heuristics for Hamiltonian cycles that exist. For example, this link claims that if the graph is dense enough, with all degrees at least $$$n / 2$$$, a cycle always exists and you can find one in $$$O(n^2)$$$ (the link talks about paths since that was the original question, but the proof mentions cycles). Also, since the problem doesn't provide instructions on what to do if there's no solution, you can deduce the test cases always guarantee at least one cycle exists, so the graphs are probably somewhat dense because author had to write a generator that generates valid test cases somehow, and that's much easier with dense graphs.

If you don't mind, you can send me the problem statement, because I'm Vietnamese too, anh I can read it