考场上写了个假算法/cf
首先我们可以发现不会有无解的情况，因为全部染同一种颜色即可。
其次如果所有边都没有定向，那么任取一个点，作外向树即可达到最大值 \(n-1\)。
现在有一些边是定向的，另一些边是没有定向的。我们取一个根，将所有没有定向的边都造成从这个根出发的外向树。那么对于这样的树来说，答案的一个下界是外向边个数。
同时我们发现，如果外向边个数不等于这个下界，那么会出现形如 \(x\) 个外向， \(y\) 个内向相连，并且 \(y>x\) 的情况，这样将根换到这条链的另一端会更优，所以选取这个下界最大的根，答案就是这个下界。这个根可以换根 dp 出来。
这样的话每条边都被定向了，因此构造方案也是简单的：从这个根开始 dfs，维护一个颜色栈，如果走过一条正向边就分配一个新的颜色，否则取出栈顶的颜色和它配对。因为上面的性质保证在取出栈顶的时候栈一定不为空，所以一定可以构造出这样的一个方案。