被折磨哩QAQ。

A

做法

每个点拆成两个点，如果有一条边 $(x,y)(x<y)$ ，那么连边：$(x+n,y)$。

然后除了 $1,2n$ 以外的每个点选择一条边，其中 $2$~$n$ 表示这条边是第一棵树上指向父亲的边，而 $n+1$~$2n-1$ 表示的是这个点第二棵树上指向父亲的边。

然后检查图中是不是基环森林，每有一棵基环树答案乘 $2$ 。

时间复杂度：$O(n)$

显然，这是一个 $2n-2$ 个点和边的图，然后如果图中没有孤立点（有显然是无解的），显然构成的图就是一个基环树森林，然后一个基环树的贡献显然只有基环的两种方向。

注：代码与做法有点区别。

但本质相同。

实际上我赛场想的做法并不是这个做法，这个做法是别的队的，这个做法的最大有点就是：本质，好写。

我写写我的想法吧。

我并没有拆点，这是导致我做的慢的原因，然后，我对于一个点把边分成了两种，指向编号大的和指向编号小的，看起来和拆点类似，但是实际上差别很大，至少证明会复杂很多。

然后如果有点的某一种边只有一条且其没有选择这个方向上的父亲时，就直接选择。（补充一下，不难发现，这其实就是每一棵树/森林的叶子节点可以找到另一棵树/森林上其的父亲，然后不断确定边，最后把两棵树都拆成一堆森林）

显然，最后两棵树可能会剩下一堆森林交错，无法具体确定哪条边应该归属到哪棵树中。

因此，我们尝试先进行一次选择，即指定一个点的某条边一定在某棵树中，观察一下具体会发生什么。