设度数最小的点为 $s$，它一定是第一层的某一个点。$s$ 的度数不超过 $2m/n$，由于 $n=\Omega(\sqrt m)$，因此 $s$ 的度数不超过 $O(\sqrt m)$。

枚举 $s$ 在第二层对应的点 $t$。从 $s$ 和 $t$ 开始 BFS，则以 $s$ 为起点 BFS 到的点即为第一层的点。已知第一层的点，就可以确定第二层的点，然后依次确定所有层的点。如果过程中发现矛盾则退出。最后检查每一层内部的边是否都相同。

时间复杂度 $O(m\sqrt m)$。