SRM525 Div1 525

問題

n匹のウサギちゃんがいて、何匹かのウサギちゃんだけが知っている2つの噂をすべてのウサギちゃんに広めたい。
ただし、各ウサギちゃんが伝えられるウサギちゃんは決まっており、さらに、1日に1つの噂しかその決まったウサギちゃんに広められない。
全てのウサギちゃんに広まる最短の日数を求めよ。広めることができない場合は-1を返す。

1<=n<=16

考え方

噂を知っているならば、すぐにその噂を広めないといけない。噂を広めるときは、各ウサギちゃんは高々2回広めればよい。

各ウサギちゃんが噂を受け取った次の日にその噂を周りに広めればよいが、二つの噂を知っているとき、どちらの噂を優先的に広めればよいかが問題となる。
もし、この優先度があらかじめ決まっているのならば、その優先度に従って噂をすぐに広めるシミュレーションをすれば何日かかるかがわかる。
どちらの噂を優先的に選ぶかは2^n通りで、m日間広めるシミュレーションがn^2通りなので、全体で2^n * m * n^2 = 約3.0 * 10^8となり間に合わなそうに見えるが、実際はn^2がそんなに大きくならない(みたい)。

2^nはビット演算を使うと便利。