E - Odd Cycle 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 450 点

問題文

頂点に 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 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 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
  • 与えられるグラフは単純連結無向グラフである
  • 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

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

条件を満たす数列が複数存在する場合、どれを出力しても正解となる。

入力例 1

4
3 3
1 2
2 3
1 3
7 7
1 2
2 3
3 4
1 4
4 5
5 6
6 7
5 5
1 2
2 3
3 4
4 5
1 5
9 10
1 2
2 3
3 4
4 5
1 5
6 7
7 8
8 9
6 9
1 6

出力例 1

3
2 1 3
-1
5
3 2 1 5 4
5
3 2 1 5 4

一つ目のテストケースでは、数列 (2,1,3) が条件を満たします。(2, 1), (1, 3), (3, 2) のいずれも辺として存在します。また v = (2, 3, 1) などを出力しても正解となります。

二つ目のテストケースでは、奇数個の頂点からなる閉路はないため条件を満たす数列は存在しません。

Score : 450 points

Problem Statement

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.

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.

Input

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

Output

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 Input 1

4
3 3
1 2
2 3
1 3
7 7
1 2
2 3
3 4
1 4
4 5
5 6
6 7
5 5
1 2
2 3
3 4
4 5
1 5
9 10
1 2
2 3
3 4
4 5
1 5
6 7
7 8
8 9
6 9
1 6

Sample Output 1

3
2 1 3
-1
5
3 2 1 5 4
5
3 2 1 5 4

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.