比赛：CF2127 Div.1+2

如果 $a_i$ 为 $0$，等价于要求 $\mathrm{mex}=\max$，无解。

否则，等价于要求 $\max=\min$，则所有数都要相等才有解。

容易发现只朝一个方向走最优。

把 $a_i$ 和 $b_i$ 看作区间 $[a_i,b_i]$ 或 $[b_i,a_i]$，

若存在两个区间有交，Ali 一直选择这两个区间即可，答案和原序列相同。

否则，Ali 选择两个距离最近的区间，然后后面一直选这两个。

首先必须是树才有解。

发现一个点连向对岸的点，必须在对岸构成一段区间，且这些区间两两的交 $\le 1$。

于是可以想到，若一个点的邻点中，$\mathrm{deg} > 1$ 的点的数量 $>2$，则无解，因为 $\mathrm{deg} > 1$ 的点一定要放在区间的端点。

然后除去邻点中度数大于 $1$ 的点，剩下的点可以随意排列，乘上阶乘。

然后如果两岸都有 $\mathrm{deg} > 1$ 的点，最后答案乘 $2$，因为可以把每个方案两岸同时翻转。否则翻转后和原来的方案等价。

最后答案还要乘 $2$，因为每个方案对岸可以互换。

考虑自底向上填，发现点 $u$ 的颜色若不确定，如果子树中有任意已经确定颜色的点，那么一定可以在子树中找到一个颜色作为点 $u$ 的颜色，使得方案最优，且不会对更上层的节点产生影响。

否则，若整个子树都没颜色，我们放到最后再处理。

进行完初步确定后，如果整棵树都没颜色，全部设为 $1$ 即可；否则，从上往下确定颜色，让没确定的节点颜色等于父亲节点的颜色。

用 set 启发式合并维护子树颜色即可。