問題リンク

解説

単調性があるのは自明なので二分探索をします。

二分探索をすると、ダメな関係にedgeを結んだとき、このedgeで結んだところを一緒にしないように二つのグループに分けられるかという問題になります

これはまさしく二部グラフ判定なので、この問題は解けました

提出コード

https://tlx.toki.id/problems/troc-16/D/submissions/735775