AT_abc472_e [ABC472E] Odd Cycle

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\le i \le K $ , there is an edge between vertices $ v_i $ and $ v_{i+1} $ , where $ v_{K+1} = v_1 $ . You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ M $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ \vdots $ $ a_M $ $ b_M $

For each test case, if there is no sequence satisfying the conditions, output `-1`. If one exists, output one such sequence in the following format: > $ K $ $ v_1 $ $ v_2 $ $ \ldots $ $ v_K $ If multiple sequences satisfy the conditions, any of them will be accepted.

### Sample Explanation 1 In the first test case, the sequence $ (2,1,3) $ satisfies the conditions: the edges $ (2, 1), (1, 3), (3, 2) $ all exist. Outputs such as $ v = (2, 3, 1) $ are also accepted. In the second test case, there is no cycle with an odd number of vertices, so no sequence satisfies the conditions. ### Constraints - $ 1 \le T \le 2\times10^5 $ - $ 1 \le N, M \le 2\times10^5 $ - The sum of $ N $ over all test cases is at most $ 2\times10^5 $ . - The sum of $ M $ over all test cases is at most $ 2\times10^5 $ . - $ 1 \le a_i,b_i \le N $ - $ a_i\ne b_i $ - The given graph is a simple connected undirected graph. - All input values are integers.