$n=5000$，看起来是 $O(n^3)$ 但是 200ms 过了。

• 按度数排序，此时 $deg_i\ge deg_{i+1}$。
• 正序枚举 $i$
• 正序枚举 $j<i$
• 枚举 $k$，判断是否存在 $i\to k\to j$ （两条边）的路径。若存在 $i\to j$ 的路径（只有一条边）则略去这一步。
• 若 $\forall j<i$ 存在 $i (\to k) \to j$，认为 $i$ 合法。
• 搜到三个合法的 $i$ 结束程序，否则搜到最后并输出 $-1$。

这有什么道理吗。有没有人会hack或证明。