島の連結性には，日付に対する単調性があります．具体的には

• \(t\) 日目にすべての島が連結であるならば，\(t-1\) 日目にもすべての島は連結である．
• \(t\) 日目にすべての島が連結でないならば，\(t+1\) 日目にもすべての島は連結でない．

を満たします．

したがって，日付に対する二分探索でこの問題を解くことができます．「\(X\) 日目にすべての島が連結か」という判定問題は \(1\) 回の BFS によって判定できるため，時間計算量 \(O((N + M) \max D_i)\) で解け，本問の制約下で十分高速に解けます．