类似 $\texttt{meet in the middle}$，第一遍 $dfs$ 先搜索前 $k$ 个点，对于搜索出来的一个集合 $S$（$|S|\le k$），如果 $S$ 内部合法（不考虑后 $n-k$ 个点）那么 $f_S=|S|$，否则 $f_S=0$。

然后对 $f_S$ 做一遍高维前缀 $\max$，之后 $f_S$ 的含义就变为 $S$ 的子集中，内部不矛盾的集合大小的最大值。

第二遍 $dfs$ 搜索后 $n-k$ 个点，对于搜索出来的一个集合 $S$，同时维护 $T$。其中 $T$ 是满足 $T$ 与 $S$ 不矛盾的最大集合，不难发现只有 $T$ 的子集不与 $S$ 矛盾。则 $S$ 的贡献为 $|S|+f_T$，答案就是所有贡献的最大值。

接下来分析时间复杂度，第一遍 $dfs$ 及高维前缀 $\max$ 预处理的复杂度为 $O(k\cdot 2^k)$，第二遍 $dfs$ 的时间复杂度是 $O(2^{n-k})$，因此总时间复杂度为 $O(k\cdot 2^k+2^{n-k})$。

通过打表发现 $k$ 取 $\max(1, \frac{n}{2}-2)$ 的时候最优。