以 $xht$ 的题解举例
其实第 $3$ 类边是 $\mathcal O(n)$ 的，考虑同一节点每个颜色的边最多只有两条，超过两条一定无解，所以第 $3$ 类边可以不用前缀优化