口胡题解，没写代码。怕忘了所以记录一下。

我们发现如果确定了 $p_1$，那么就能唯一确定整个 $p$。

具体过程是，设当前走到 $u$，如果 $u$ 的出度 $>1$ 那么无解，否则将 $u$ 变为它唯一的出度指向的点。

此时我们得到了一个 $O(nm)$ 的做法。

假设我们已经有一组合法解 $p$，考虑怎么求出所有的解。

考虑 $p_n$ 的最长的回溯边，设它能回溯到 $p_i$。

显然其它解的起点必须在 $p_{(i,n]}$ 中。

如果 $[i,n)$ 中存在一个 $j$ 满足 $p_j$ 的最长回溯边能回溯到 $p_i$ 之前的点，那么显然其它解的起点必须为 $p_{j+1}$。

否则一定要有 $i=1$ 才可能有其它解。我们考虑所有除了 $p_n\rightarrow p_1$ 的回溯边。设其中一条为 $p_r\rightarrow p_l$，那么其它解的起点一定不能在 $p_{(l,r]}$ 中。同时，在考虑完所有回溯边的限制之后，剩下的点一定可以作为某个解的起点，求出解的哈希值也是容易的。

现在考虑怎么求出一组合法的 $p$。

初始设 $\forall u,z_u=0$。

我们每次找出一个还未访问过的出度为 $1$ 的点 $S$，然后从它开始走。

设当前走到 $u$，那么有如下三种情况：

• 如果 $z_u=0$，那么将 $z_u$ 变为 $S$。
• 如果 $z_u=u$，那么将所有 $z=u$ 的点的 $z$ 都变为 $S$。
• 否则，$S$ 和 $z_u$ 不共戴天，设 $S$ 和 $z_u$ 走到 $u$ 之前的一步走到的分别为 $v_1,v_2$。那么对于任意一组解 $p$，都有 $p_n=v_1$ 或 $p_n=v_2$。而确定 $p_1$ 和 $p_n$ 中的任何一个就可以唯一确定整个 $p$，因此直接把这种情况特判掉即可。

需要注意的是，如果出现了 $z_u=u$ 的情况，我们需要一步跳到最后一个 $z_u=u$ 的位置，否则不能保证复杂度正确。

这个过程可以用 并查集 + 启发式合并 做到 $O(m\log n)$。