$x$ 合法，可以推出 $x$ 无横叉边和前向边并且子树同理。

对于一个点 $x$ 合法（即好点），当且仅当 $x 为根或者有且仅有一条返祖边 $u\rightarrow v$ 覆盖 $x$ 且 $v$ 合法。

$n\le 5000$ 找竞赛图。

考虑从 $1\rightarrow n$ 插入每个点，若指向当前全部点，放链头，若全部被指向放链尾，否则找到第一个它指向的，保存下来，最后一个指向它的。

易证最后若是链无解，否则存在大小 $\ge 3$ 的环，因此也一定能找到三元环。

$O(n^2)$

$\le 20000$ 次询问，可以查询点集 $S$ 内的边的数量，要求判断图是否可以构成二分图，可以则输出一个集合，不可以则输出任意一条奇环。

我们每次考虑一个点的所有连边，对每个点执行重复操作，最终可以构建 $dfs$ 树，并有若干返祖边。

考虑二分图性质，只有两个集合，且集合内无连边。

该性质还可以推出二分图内无奇环。

那么我们可以这样判断一个点的所有连边。

对于集合 $S$ ， $T$ 。
若两个集合内有连边则边的个数为 $f(s\cup T)-f(S)-f(T)$ ，我们考虑分治处理（大区间若含有边则边一定存在于小区间），因此就可以确定边了。

那么有解的情况就是，深度为奇数的点集合，和偶数的两个集合，最后询问一下集合有无连边，无连边则证明有解。

无解情况，考虑只要找到同一集合的连个点，再找到与其都经过的另个集合中的点，三点加若干路径上的点必然能构成奇环，暴力跳父亲即可,因为奇偶交错，父亲一定再答案集合中。

查询次数约为 $2\times n \log n \frac{1}{2}$ + $2 \times n\log n$ 复杂度不可能严格，因为集合处于变动，趋于中央。

启发：分治处理询问，寻找单调性。

__END__