先考虑怎么确认 Q，一个最简单的想法就是一定能取到下界，也就是 $\sqrt {2n-2}$，但是非常可惜他是错的，不过容易发现大不了多少，考虑从这个下界开始从小到大枚举判合法。

有一个很明显的错解是从大到小塞进去，肯定是错的。

我们考虑随机打乱然后再塞进去并重复 1 次，哇他对了。

然后考虑如何构造方案，先把颜色相同的点缩到一起，然后每次考虑如果有之前选过的点指向他，那就把这条边的颜色存下来，然后最后会存出一个序列，优先考虑这个颜色序列中的节点。

因为每个颜色都占了至少一条边，那你给他安排好，就一定会空出来一条边，所以我一直这样选一定可以最后选完，而之前没出现过的颜色就更不用说了。

唯一的可能是连出去的 $Q$ 条边连过来的颜色全部相同，但是你容易发现如果有 $Q$ 条边，说明一定存在重边，那就不可能颜色都相同，所以没问题。

感觉这个构造很人类。