算法一（特殊性质）

如果 $g$ 成环，那么显然无解。否则考虑 $g$ 构成的有根树森林，只需要从叶子节点往上不断执行 $\text{unite}$ 操作即可。操作次数和时间复杂度都是 $\mathcal{O}(n)$ 的，期望得分 $36$ 分。

算法二

同样先判掉成环或者初始时连通，但最终不连通的情况，这一定无解。

设初始时有 $k$ 颗树 $T_1\sim T_k$，根分别为 $r_1 \sim r_k$。假设最终状态只由一颗树构成，考虑由这 $k$ 个根在最终状态构成的树的结构：如果 $x$ 是 $y$ 的父亲，那么必定是某一步 $y$ 直接合并到 $x$。这是因为，$\text{find}$ 操作只会将具有祖先后代关系的一组点的祖先后代关系破坏，而不会增加新的祖先后代关系。所以，如果最终时刻有限制 $x$ 必须是 $y$ 的祖先，那么在任意时刻该限制都需要满足。

接下来考虑，如果最终某个 $r_x$ 的子树内存在点 $u$，使得 $u$ 在初始时位于另一棵子树 $r_y$ 中，那么在某一时刻 $r_x$ 是 $r_y$ 的祖先。因此我们可以得到若干形如 $r_x$ 必须是 $r_y$ 祖先的限制。如果限制成环，显然无解。否则跑出任意一组拓扑序，按照拓扑序来构造方案。

注意到如果 $x$ 是根，$y$ 是 $x$ 的某一个儿子，$z$ 是 $y$ 的某一个儿子，那么我们可以通过操作 $z$ 来将 $z$ 所在子树提到 $x$ 的儿子，而其他结构没有影响。同时，注意到，对于初始时非根节点 $t$，$t$ 与 $fa$ 在最终具有父子关系，当且仅当 $t$ 没有被操作过。于是我们可以据此判定是否要在某个时刻操作 $x$。因此我们可以知道在初始时需要对哪些点先进行 $\text{find}$，在初始时便进行这样的操作一定是最优的。

因此我们直接按照拓扑序依次复原即可。另外还需要注意一些细节，如果初始时做完 $\text{find}$ 操作后有节点需要到其他子树，但连向的不是根，这种情况也是无解的。总之实现起来并不容易，大样例里非常良心地考虑到了所有情况，可惜似乎没人来做这个题，难过了。

由于做到一个点时至多进行 $n$ 次操作，因此操作次数不会超过 $n^2+n$。时间复杂度 $\mathcal{O}(n^2)$。期望得分 $100$ 分。