腰带图
题号：NC15195
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

一个n个点m条边的无向图，它若满足以下性质，我们就称它为腰带图：

1.n为>=6的偶数。
2.这个图恰有3/2*n条边。
3.存在所有点的一个排列p0,p1,...,pn-1，使得对于所有满足0<=i<n/2的整数i：

(1)点pi和点p(i+1) mod (n/2)间有边相邻。

(2)点pi+n/2和点pn/2+(i+1) mod (n/2)间有边相邻。

(3)点pi和点pi+n/2间有边相邻。

注：x mod y为x除以y的余数。

现在给你一个无向图，请判断他是否是腰带图。

输入描述:

输入的第一行有一个正整数T，代表询问数。
每个询问各占1+m行，当中的第1行有两个正整数n,m分别代表点数和边数，接下来m行当中的第i行包含两个整数xi,yi，代表点xi和点yi间有边相连。

输出描述:

每个询问的回答占1行，若此图不是腰带图，该行里只包含一个整数-1；
若是腰带图，则输出n个数p0,p1,...,pn-1，其为任一个能证明此图是腰带图的0~n-1的排列。(意思就是题面里提到的该有的边都存在。)
示例1

输入

复制 
3
6 9
0 1
1 2
2 0
3 4
4 5
3 5
0 3
1 4
2 5
8 12
0 1
0 2
0 3
4 5
4 6
4 7
1 5
1 6
2 6
2 7
3 7
3 5
6 9
0 1
0 2
0 3
0 4
0 5
1 2
1 3
1 4
1 5

输出

复制 
0 1 2 3 4 5
0 2 7 3 1 6 4 5
-1

备注:

1<=T<=200
6<=n<=200
3n=2m
0<=xi,yi<n
xi!=yi
若i!=j,(xi,yi)!=(xj,yj)