You are given a simple connected undirected graph with $$$N$$$ vertices numbered $$$1$$$ through $$$N$$$ and $$$M$$$ edges. The $$$i$$$-th edge connects vertices $$$a_i$$$ and $$$b_i$$$.

Determine whether there exists a cycle consisting of an odd number of vertices, and if one exists, find one such cycle.

Formally, determine whether there exists an integer sequence $$$(v_1,v_2,\ldots,v_K)$$$ satisfying all of the following conditions, and if one exists, find one such sequence.

• $$$K$$$ is an odd number at least $$$3$$$.
• $$$v_1,v_2,\ldots,v_K$$$ are all distinct.
• For every integer $$$i$$$ with $$$1\leq i\leq K$$$, there is an edge between vertices $$$v_i$$$ and $$$v_{i+1}$$$, where $$$v_{K+1}=v_1$$$.

Constraints

• $$$1\leq T\leq 2\cdot 10^5$$$
• $$$1\leq N,M\leq 2\cdot 10^5$$$
• The sum of $$$N$$$ over all test cases is at most $$$2\cdot 10^5$$$.
• The sum of $$$M$$$ over all test cases is at most $$$2\cdot 10^5$$$.
• $$$1\leq a_i,b_i\leq N$$$
• $$$a_i\neq b_i$$$
• The given graph is a simple connected undirected graph.

If a simple connected graph $$$G$$$ contains a cycle with odd length, then it will not be a bipartite graph. We can simply prove this by assuming the first vertex in the cycle with black then assign the other vertices colors in order before arriving a contradiction that the first vertex should be black and white.

//#pragma GCC optimize("O3", "Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
int n, m;
vector<int> g[N];
int from[N], d[N], dd[N];

void run(){
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        int x, y; cin >> x >> y;
        g[x].push_back(y); g[y].push_back(x);
    }
    if (m == n - 1){
        cout << -1;
    }
    else {
        queue<int> b;
        d[1] = 0; b.push(1); from[1] = -1;
        while (!b.empty()){
            int u = b.front(); b.pop();
            for (auto i : g[u]){
                if (!dd[i]){
                    dd[i] = 1; from[i] = u; d[i] = d[u] + 1; b.push(i);
                }
            }
        }
        int u = -1, v = -1;
        for (int i = 1; i <= n; i++){
            for (auto j : g[i]){
                if ((d[i] + d[j]) % 2 == 0){
                    u = i; v = j; break;
                }
            }
        }
        if (u == -1){
            cout << -1;
        }
        else {
            deque<int> x;
            while (1){
                if (u == v){
                    x.push_back(u); break; //final vertex of the odd cycle
                }
                x.push_back(u); x.push_front(v); //push from two ends
                u = from[u]; v = from[v];
            }
            cout << x.size() << "\n";
            for (auto i : x) cout << i << " ";
        }
    }
    for (int i = 1; i <= n; i++){
        g[i].clear(); dd[i] = 0; from[i] = 0; d[i] = 0; //resetting the array for future queries
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);    

    
    int t = 1; cin >> t;
    while (t--){
        run(); cout << "\n";
    }

    return 0;
}