一个n个点m条边的无向图，它若满足以下性质，我们就称它为腰带图： 1.n为=6的偶数。 2.这个图恰有32*n条边。 3.存在所有点的一个排列p0,p1,...,pn-1，使得对于所有满足0 (1)点pi和点p(i+1) mod (n2)间有边相邻。 (2)点pi+n2和点pn2+(i+1) mod (n2)间有边相邻。 (3)点pi和点pi+n2间有边相邻。 注：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
备注:
163n=2m0i,yixi!=yi若i!=j,(xi,yi)!=(xj,yj)
加载中...