入力

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

T
N M
a_1 b_1
a_2 b_2
:
a_M b_M

N M
a_1 b_1
a_2 b_2
:
a_M b_M

N M
a_1 b_1
a_2 b_2
:
a_M b_M
:
:
:
N M
a_1 b_1
a_2 b_2
:
a_M b_M

• 1 行目にはテストケース数 T が与えられる。
• 2 行目から T 個、テストケースの情報が与えられる。各テストケースの情報は以下の通り。
• テストケースのうち 1 行目に、頂点数と辺数 N, M が与えられる。
• テストケースのうち 2 行目から M 行には、a_i, b_i(0 ≦ a_i, b_i < N) が与えられる。これは辺 (a_i, b_i) を表す。
• テストケースとテストケースの間には空行が挟まっている。
• 多重辺、自己ループは無いが、グラフは連結とは限らない。

出力

T 行出力する。i 行目には、i 番目のテストケースで求めた最大マッチングを出力する。

具体的には、空白区切りで N 個の出力をする。i 番目には頂点 i のマッチング相手を出力する。マッチングしない場合は -1。

たとえば、頂点数が 5 で、(0, 4) と (1, 2) をマッチングさせたいなら以下のように出力。

4 2 1 -1 0

テストケース詳細

テストケースは全部で 5 ケースあり、以下のようになっています

Case1: T = 5000, 1 ≦ N ≦ 8 ランダムグラフ
Case2: T = 5000, 10 ≦ N ≦ 20 ランダムグラフ
Case3: T = 500, 50 ≦ N ≦ 100 ランダムグラフ
Case4: T = 50, 200 ≦ N ≦ 300 ランダムグラフ
Case5: T = 10, 200 ≦ N ≦ 300 マッチングする辺を決めて、最大マッチングがそれを超えない限り辺を追加し続けたグラフ