考虑随机染色之后跑弗洛伊德类似的东西，这样可以有效的避免出现奇环。

因为路径的长度最大只有 $10$，所以染错的概率只有 $\frac{511}{512}$，跑个 $5000$ 次就可以过了，注意需要使用随机种子否则将会体验到 CodeForces 可以随便 Hack 的恶意。