問題

考察の流れ

高橋キングダム島ありすぎワロタ　（3 $\leq$ $N$ $\leq$ 2×10⁵）

グラフを使ってあれやこれやする感じなのかな…？と思いかけたけどよくよく見ると島1から島Nまで，どこか一つの島Xを経由していけるなら構わないということになる．

愚直にやろうとすると島1から定期便で行ける島全てに対して，さらにその島から行ける島全てを見て，その中に島Nがあるか調べればいい．これはO(N²)で，島多すぎワロタなので間に合わない．

計算量を落とす方法を考えなくてはいけなくなった…が，前記事ABC 073 C問題 Write and Erase - おふとん王国でsetを復習してたこともあり，setを使えないかと考える．

入力を受け取るときに，島1，島Nへの定期便がある島をそれぞれsetで持っておいて，各setに共通要素がないか見ていけばいい．

島1に行ける島のsetから全部要素を取り出し（O(N)），その要素が島Nに行ける島のsetにあるか調べる（O(log N)）ようにすれば，計算量はO(N log N)で間に合わせることができる．

1発AC　所要時間20minくらい