Step 1: Does the graph have a cycle? If not print -1.
Step 2: Remove all bridges. Then each and every edge will be part of a cycle.
Step 3: Find out the vertex with most .edges. If there are multiple choose the smallest such vertex
Step 4: Delete the vertex and remove all its edges.
Step 5: Does graph still have a cycle? If so, print -1. If not, print vertex number.
i have a simple idea, i wish it will be useful :
you can use properties of cycle in graph (the difference between tree and graph)
if the number of edges in a connected components is more than the number of vertex - 1 --> we have cycle in this connected :
step 1 : if we have found an answer before : print -1 and break everything
step 2 : sort the vertexes which belong to last connected (store it when you visited it) and try to apply DFS on it from smaller one but make sure, you have to pass it and don’t visit it, and you can pass some of them by try to delete its edges and compare (this condition will make deference for saving time)
count the number of edges in the new connected (maybe will appear more than one) and compare it , if you don’t have a cycle then the answer will be the last vertex you tried to delete it
if you don’t find the suitable vertex then print -1 and break everything
step 3 : continue the searching for more connected components, if you finish without a break then print the answer (don’t forget you have to make the answer = -1 before you start the searching)