To get straight to the point, the following algorithm is valid:

• Take a spanning tree, and color each vertex with \(0\) or \(1\) so that \(C_u \ne C_v\) for all edge \((u, v)\) in the spanning tree.

• Inspect each edge \((u, v)\) not contained in the spanning tree.

  • If \(C_u = C_v\), take the vertex sequence forming the \((u, v)\) path on the spanning tree, which is what we want; print it and terminate the program.

  • If \(C_u \ne C_v\), ignore it.

• If the program has not been terminate, there is no odd cycle.

Proof

First, let us verify that the vertex sequence found by this algorithm is valid. It is easy to check that it forms a cycle. Moreover, the tree has alternating colors like \(0, 1, \dots, 1, 0\), so having the same color for the endpoints imply there is an odd number of vertices.

Conversely, if this algorithm did not found one, all edge \((u, v)\) satisfies \(C_u \ne C_v\). This suggests that traversing an edge always flips the color, so any cycle starting from and ending at a color-\(0\) vertex traverses an even number of cycle (same goes for color \(1\)). Thus, this graph does not have an odd cycle.

Such a graph, “without an odd cycle” \(\Leftrightarrow\) “colorable with \(0\) and \(1\),” is called a bipartite graph.

Sample code

Several tricks are adopted for simplicity. First, we construct a spanning tree and check the color simultaneously.

Moreover, instead of actually finding a \((u,v)\)-path in the spanning tree, we take the \((u,1)\) path and \((v,1)\), and then cancel out the common part up to the branch.

def solve():
    n, m = map(int, input().split())
    g = [[] for _ in range(n)]
    for i in range(m):
        u, v = map(int, input().split())
        g[u-1].append(v-1)
        g[v-1].append(u-1)
        
    c = [-1] * n
    p = [-1] * n
    c[0] = 0
    
    st = [0]
    while st:
        u = st.pop()
        for v in g[u]:
            if col[v] == -1:
                col[v] = col[u] ^ 1
                par[v] = u
                st.append(v)
            elif col[u] == col[v]:
                a, b = [], []
                
                x = u
                while x != -1:
                    a.append(x)
                    x = p[x]
    
                x = v
                while x != -1:
                    b.append(x)
                    x = p[x]
    
                while a[-1] == b[-1]:
                    w = a.pop()
                    b.pop()
    
                ans = a + [w] + b[::-1]
                print(len(ans))
                print(*[x+1 for x in ans])
                return 
    
    print(-1)
    return 

t = int(input())
for i in range(t):
    solve()