問題

考察

無向グラフがあります。連結している頂点の集まりを「島」と呼ぶことにします。問題では島が2つあることが保証されてます。そして頂点$1$と頂点$N_1 + N_2$は必ず別々の島にあることも保証されています。それぞれの島のいずれかの頂点を辺で結びたいです。さらにこの時、頂点$1$と頂点$N_1 + N_2$との距離がありえる中で最大にしたいようです。そのあり得る距離を求めてくださいという問題です。(問題ページの「入力例・出力例1」に掲載されている図を見ると理解しやすいです。)

頂点$1$と頂点$N_1 + N_2$まで移動するには、新たに結ぶ辺を通る必要があります。そのため、「頂点$1$を含む島の中で頂点$1$からの距離が最大の頂点」と「$N_1 + N_2$を含む島の中で頂点$N_1 + N_2$からの距離が最大の頂点」同士に新たに辺を結べば題意を満たす無向グラフになります。これが分かれば下記の式に当てはめれば答えが出てきます。
$$(頂点1を含む島の中で頂点1からの距離が最大の頂点との距離) + (頂点N_1 + N_2を含む島の中で頂点N_1 + N_2からの距離が最大の頂点との距離) + 1$$
あとは「頂点$1$を含む島の中で頂点$1$からの距離が最大の頂点との距離」と「$N_1 + N_2$を含む島の中で頂点$N_1 + N_2$からの距離が最大の頂点との距離」を求めていきましょう。
これについては、「幅優先探索」という探索手法を使えば大きくない計算量で求めることができます。それぞれの距離を求めるために、下記の2通りの幅優先探索を行いましょう。

頂点$1$を始点として、島の中で幅優先探索
頂点$N_1 + N_2$を始点として、島の中で幅優先探索

幅優先探索で各頂点の距離を求める実装方法は下記の記事が参考になります。

これで答えを求めることができます。

提出コード(コンテスト後)

ご不明点などがあれば教えていただけると幸いです。

参考