This solution is giving wrong answer in 3 test cases which are very large and i am unable to debug those Please Help....;)
bool dfs(int node, vector<int> adj[], int vis[], int par, stack<int> &st) {
vis[node] = 1;
st.push(node);
for (auto x : adj[node]) {
if (!vis[x]) {
if (dfs(x, adj, vis, node, st)) {
return true;
}
}
else if (x != par) {
st.push(x);
return true;
}
}
return false;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n, m;
cin >> n >> m;
vector<int> adj[n + 1];
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
adj[x].pb(y);
adj[y].pb(x);
}
stack<int> st;
int vis[n + 1] = {0};
int fl = 0;;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
if (dfs(i, adj, vis, -1, st)) {
fl++;
break;
}
}
}
if (fl) {
vector<int> ans;
int x = st.top();
ans.pb(x);
st.pop();
while (st.size() > 0 && st.top() != x) {
ans.pb(st.top());
st.pop();
}
ans.pb(x);
cout << ans.size() << endl;
for (auto x : ans)
cout << x << " ";
}
else
cout << "IMPOSSIBLE";
}