Solution
由于合法答案要求每个点最多有一个未经过的出点，则每个起点至多对应一个合法排列。
最多有 $O(n)$ 条链，暴力找时间复杂度 $O(nm)$。
发现答案达到 $O(n)$ 级别当且仅当合法链的链尾连向链头，给出一个构造性证明：
初始认为每个点单独成链，然后对链尾有且仅有指向一个链外点的链找新链合并，得到一个极大的链覆盖方案。
如果合法链的链尾连向链头，则构造一定产生 $1$ 条链尾连向链头的合法链，一共有 $O(n)$ 个候选置换。
如果构造得到 $1$ 条链尾不连向链头的链，则最多产生 $2$ 个合法链。证明：若起始位置不为链头，则其在环上的相对位置为 $[pos_k,n],[pos_{k-1},pos_k-1],\cdots,[1,pos_1-1]$。而如果 $n$ 存在多个回边，则开头一定在最小回边右侧最左侧存在一条回边穿过交界处的位置，否则走到链尾产生非法状态。
如果构造得到 $\ge 2$ 条链，则最多产生 $2$ 个合法链。证明：每个合法链头一定在某个极大链的链头处，其满足链尾有且仅有指向一个链外点，记为候选链。其一定不连向链头，则会切断另一条极大链，形态为 $A\to [B_p,B_{back}]\to C\to D\to \cdots\to [B_{front},B_{p-1}]$。一条候选链切开的链若是候选链，则其一定不会再切开新的链；否则若在后面遇到候选链，其只能切开被切开链的前缀，然后用回边解决前缀的前缀。所以候选链数量 $\le 2$。
需要求每一种构造方案，对这个证明的 $3$ 部分分别构造：
发现一条链如果不能继续合并，则以后也不能继续合并，用并查集合并链，链表维护链做到 $O(n+m\alpha(n))$。
需要判断每种候选置换是否合法，限制在于回边，利用差分即可 $O(m)$ 得到区间非法位置，每次轮换预处理 $10^k$ 容易做到 $O(1)$。
$O(n)$ 找到第二个候选开头，暴力判断即可。
判断每条链是否为候选链，如果候选链 $\ge 3$，则都是非法的，否则暴力判断即可。
总时间复杂度：$O(n+m\alpha(n))$