Cool

I too solved this problem in another way:

We can run a dfs from any arbitrary node, and store the distances of each node traversed, , which is calculated as dist[node] = dist[parent]+1. (Note that this does not represent the shortest distance from the chosen source node, since it’s not a bfs)

Let’s say we are currently at node u in the traversal, and one of its neighbours, v, is visited and (dist[u]-dist[v]) is even. Then we have found an odd length cycle, whose nodes we can find by simply backtracking on the parent array.

ORZ.. i can not solve in contest.. you are my hero

my solution was a lil different i first did a BFS and found the FIRST conflicting edge (u, v)

if there is none the answer is -1

we know that there exist a path from u to v alternating colors assigned using BFS since its the FIRST conflicting edge

you can do something like this

V<bool>vis(N);
    V<ll> chain;
    auto dfs = [&](auto &dfs, ll node){
        if(vis[node]) return;
        vis[node]=1;
        chain.push_back(node);
        if(node ==p.second) {
            cout<< chain.size() << endl;
            for (ll x : chain){
                cout << x + 1 << endl;
            }
            return;
        }
        for (ll nei:to[node]){
            if (col[nei]==col[node])continue;
            dfs(dfs, nei);
        }
        chain.pop_back();
    };
    dfs(dfs, p.first);

where p.first and p.second are the nodes of the conflicting edge

You have created a spanning tree too. $$$from_i$$$ is the parent of vertex $$$i$$$ in your tree created by the BFS.

I solved it in a similar way using DFS. When I found an odd cycle using bi-coloring, I stored the parent and child nodes and immediately returned from the function. Then, I backtracked from the child to the parent to get the cycle.

#include <bits/stdc++.h>
using namespace std;

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define endl '\n'
#define int long long

bool isCycle;
int a = -1, b = -1;

vector < vector < int > > adjList;
vector < int > parent;
vector < int > color;

void dfs(int cur) {
    for (auto x: adjList[cur]) {
        if (isCycle) {
            return;
        }
        if (color[x] == 0) {
            parent[x] = cur;
            color[x] = (color[cur] == 1 ? 2 : 1);
            dfs(x);
        } else if (color[x] == color[cur]) {
            isCycle = true;
            a = x;
            b = cur;
            return;
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    adjList.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adjList[x].push_back(y);
        adjList[y].push_back(x);
    }
    parent.assign(n + 1, -1);
    color.assign(n + 1, 0);
    a = -1, b = -1;
    isCycle = false;
    for (int i = 1; i <= n; i++) {
        if (color[i] == 0) {
            parent[i] = -1;
            color[i] = 1;
            dfs(i);
        }
    }
    vector < int > ans;
    if (isCycle) {
        ans.push_back(b);
        while (parent[b] != a) {
            ans.push_back(parent[b]);
            b = parent[b];
        }
        ans.push_back(a);
        cout << ans.size() << endl;
        for (auto x: ans) {
            cout << x << " ";
        }
        cout << endl;
    } else {
        cout << -1 << endl;
    }
}

signed main() {
    FAST_IO;
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
      // cout << "Case " << i << ": \n";
      solve();
    }
    return 0;
}

Brilliant solution. I solved it by Tarjan's algorithm, and Tarjan's algorithm is too much for this task, thank you for this idea!

damn god