Is it possible to perform some sort of pre-processing that would allow to answer the question efficiently (fast)?
The graph is connected, undirected, has no self loops neither parallel edges (a cycle is formed by at least three nodes).
Note that this a yes/no query, meaning that I just need to know whether such a cycle exits, which one doesn't matter.
Preprocessing should be efficient as well (ideally less than $O(m^2)$ both time and space) where $m$ is the number of edges.
Edit: The cycle is simple (no vertex in the cycle is repeated)
Edit2: My progress so far and where I'm blocking:
I'm separating the graph into sub-components through articulation points, and then doubling articulation points in each sub-component they originally separated. This came from the following observation: 3 given vertices may belong to a cycle iff they all belong to a component with no articulation points. I have not proved this but I couldn't think of a counter example.
Assuming the observation above is correct (which seems very likely), the problem now is the 3 given vertices in the query may all be articulation points, in which case all of them would belong to several components, which in the worst case could lead to a slow O(n) query time complexity.
Another observation that seem helpful to address the described worst case is: there's at most 1 sub-graph to which 2 given articulation points may both belong to at the same time (I can prove this if needed), the observation easily leads to a worst case pre-processing space and time of $O(n^2)$ (n is number of vertices), versus constant time queries, however $O(n^2)$ preprocessing time is too slow ($O(n^2)$ space is also too greedy). Can preprocessing be improved for a trade off of maybe log(n) query time expense?