#P4466. [Jsoi2013]超立方体

    ID: 3700 传统题 2000ms 256MiB 尝试: 107 已通过: 31 难度: 7 上传者: 标签>难度分类提高+/省选-枚举与搜索广度优先搜索位运算位集求并构造与建模排列构造模拟与实现技巧时间戳避免清空数组CF2200By佚名上传

[Jsoi2013]超立方体

[JSOI2013] 超立方体

题目描述

超立方体是普通立方体在任意维度上的推广。把超立方体的顶点视为图中的点、把每条棱视为无向边,就得到超立方图。

从零维的点到四维超立方图,同一个坐标方向的棱用同一种颜色表示

DD 维超立方图有 2D2^D 个点。每个点可用一个不同的 DD 位二进制数表示,即编号为 00 到 2D−12^D-1。两个点之间恰好有一条边当且仅当它们的二进制编号恰好有一位不同。图中没有自环和重边。二维时这是一个正方形,四个顶点可以按顺序编号为 0,1,3,20,1,3,2。

给定一个有 NN 个点、MM 条边的无向图,判断它是否与某个超立方图同构。若同构,请给出一种符合上述规则的重新编号方案。

输入格式

第一行输入一个整数 QQ,表示询问数。

接下来 QQ 组询问。每组第一行输入 N,MN,M,分别表示点数和边数。点的原编号为 00 到 N−1N-1。

接下来 MM 行,每行输入两个不同的整数 x,yx,y,表示一条连接 xx 和 yy 的无向边,其中 0≤x,y<N0\le x,y<N。输入可能有重边。

输出格式

对于每组询问输出一行。

若图不同构于任何超立方图,输出 -1。否则按原编号 0,1,…,N−10,1,\ldots,N-1 的顺序输出每个点的新编号。新编号必须构成 00 到 N−1N-1 的一个排列。有多个可行方案时,输出任意一个即可。

样例

3
2 2
0 1
1 0
4 4
0 1
1 2
2 0
0 3
8 12
2 3
2 6
7 6
1 7
4 1
3 4
0 2
7 3
5 6
5 1
5 0
4 0
-1
-1
0 6 1 5 4 2 3 7

样例说明

第一组存在重边,第二组存在三角形,均不是超立方图。第三组给出的编号是一种可行方案。

数据范围

1≤Q≤31\le Q\le 3,1≤N≤327681\le N\le 32768,0≤M≤1060\le M\le 10^6。