Consider some cycle, not necessarily odd A1, A2, ..., Ak=A1. Let's color each vertex from the cycle in black or white so that adjacent nodes in the cycle have different colors. It's easy to see that this is possible if and only if the cycle is of even length.

From the written above we can easily use DFS to simulate the process efficiently. We will consider every strongly connected component of the graph separately, because there can't be a cycle containing nodes from two different strongly connected components (also this allows us to arbitrarily choose the initial node for the DFS explained below). Take an arbitrary vertex, color it white and run a depth-first search from it. At any moment, say we are calling DFS from V and now we are at some of its children, say U. If U is used, then if the colors of U and V are the same, then here is an odd cycle (it should be easy for you to restore the cycle). If U is not used, then color it in V's opposite color and run DFS from it.

P_Nyagolov has generally the right idea, but he's overcomplicating it a little (edit: I got AC now).

Duplicate all vertices of the graph in a new graph that has black and white vertices. Similarly, duplicate all edges so that if a->b is an edge in the original graph, then the new graph has two edges a black -> b white and a white -> b black.

Now odd cycles in the original graph are paths between v white and v black in the new graph. Therefore, there is an odd cycle that contains vertex v if and only if v white and v black are in the same SCC. If you find any vertex for which this is true, do a DFS from v white and record the path you take until reaching v black.

We have only one thing to take care of: the question asks for a simple cycle (no repeated vertices), and our formed cycle is not necessarily simple. So you should check if any node is repeated in the cycle you formed, and take only the part of the cycle between those repetitions if it happens (e.g. the cycle A B C D B F G A becomes B C D B, because B is the first repeated vertex). Due to the way we constructed our cycle, this is now guaranteed to be a simple odd cycle.

I color the nodes as P_Nyagolov said then search for an edge (u -> v) such that color[u] == color[v], I find any path of even length (BFS or DFS, visited[node][parity]) that goes from v to u and that path with the edge (u -> v) would form a cycle of odd length.

This cycle may not be simple, but it seams like the checker of the problem does not check if it's simple or not! I get RTE when I insert the cycle into a set and assert(set.size()==cycle.size()). I get Accepted without this assertion.

You can make the cycle simple by cutting out smaller cycles as ffao said, but be careful as you may cut a cycle of odd length and leave a cycle of even length! The path of even length may contain odd number of odd cycles and odd number of edges that don't belong to any cycle, or only even cycles and even number of edges that don't belong to any cycle. So once you found a cycle of odd length, cut it and print it. Otherwise, after removing all even cycles, the remaining nodes should form an odd cycle.