問題概要
無向単純連結グラフ 
が与えられます. の辺に向きをつけて を有向グラフにするが, このとき のすべてのパスの長さが 
になるようにしたいです. このように向きをつけることは可能ですか？可能なら構成の一例を示してください.
問題へのリンク
制約
解法
もし が二部グラフなら, 必ず赤から青に向けて向きをつければ構成できることは明らかです. では二部グラフではないときはどうでしょうか？
が二部グラフでないときは, は必ず一つ以上の奇サイクルを含みます. 奇サイクルは, どうやっても条件を満たすように構成できません(実験してみてください).
よって, まず を二部グラフ判定し, 二部グラフなら前述のように構築すればよく, 二部グラフでないなら No とすればよいです.
実装
二部グラフ判定は Union-Find をつかうと楽らしいです(実装では使っていません).
Submission #145192938 - Codeforces
