AT_abc472_e [ABC472E] Odd Cycle

頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点 $ M $ 辺の単純連結無向グラフが与えられます。 $ i $ 番目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結んでいます。 奇数個の頂点からなる閉路が存在するか判定し、存在するならば $ 1 $ つ求めてください。 厳密には、次の条件を全て満たす整数列 $ (v_1,v_2,\ldots,v_K) $ が存在するか判定し、存在するなら $ 1 $ つ求めてください。 - $ K $ は $ 3 $ 以上の奇数である - $ v_1,v_2,\ldots,v_K $ はすべて異なる - $ 1\le i \le K $ を満たす全ての整数 $ i $ について、頂点 $ v_i $ と頂点 $ v_{i+1} $ の間に辺がある。ただし $ v_{K+1} = v_1 $ とする $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ M $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ \vdots $ $ a_M $ $ b_M $

各テストケースについて、条件を満たす数列が存在しない場合は `-1` を出力せよ。存在する場合は以下の形式で $ 1 $ つ出力せよ。 > $ K $ $ v_1 $ $ v_2 $ $ \ldots $ $ v_K $ 条件を満たす数列が複数存在する場合、どれを出力しても正解となる。

### Sample Explanation 1 一つ目のテストケースでは、数列 $ (2,1,3) $ が条件を満たします。 $ (2, 1), (1, 3), (3, 2) $ のいずれも辺として存在します。また $ v = (2, 3, 1) $ などを出力しても正解となります。 二つ目のテストケースでは、奇数個の頂点からなる閉路はないため条件を満たす数列は存在しません。 ### Constraints - $ 1 \le T \le 2\times10^5 $ - $ 1 \le N, M \le 2\times10^5 $ - 全てのテストケースにおける $ N $ の総和は $ 2×10^5 $ 以下 - 全てのテストケースにおける $ M $ の総和は $ 2×10^5 $ 以下 - $ 1 \le a_i,b_i \le N $ - $ a_i\ne b_i $ - 与えられるグラフは単純連結無向グラフである - 入力される値はすべて整数である