### 题目大意

$( 3 \leq n \leq 10^5, 2 \leq m \leq 10^5)$

### 解题思路

Among all such settlements the robbers will choose the one closest to settlement r.
They don’t know the caravan’s route yet, but they want to know the maximum distance they will have to go in the worst case to the settlement where they will rob the caravan.

（注意二分的写法：距离越小越满足，越大越不满足，求最大）