这道题，如果使用二分加判环，会变得十分简单。
但是如何做到线性复杂度呢？
答案是广搜时同时统计答案，因为环的形成肯定是一个个扩散出去的。
细节：
关于为何\(bfs\)第一个出来的不是正确解：
\(dist[u]\)一定是最小的，但是\(dist[v]\)却不一定，根据三角不等式，\(dist[v] \le dist[u]+1\)。
由于我们的答案是两者取一个\(max\)，所以答案只会是\(dist[u]\)或者\(dist[u]+1\)
普通的宽搜，队列中的点的权值是一定具有二段性和单调性的。
也就是类似：\(x, x, x, ..., x, x + 1, x + 1, ..., x + 1\)
反证法容易证明这一结论。
现在的\(u\)是队首，\(dist[u]=x\)。
可能会存在一种情况：
当前点\(u->a\), \(dist[a]=x+1\)。
后面有一个点\(y\),\(dist[y]=x\)，\(y->b\), \(dist[b]=x\)。
这样第一次搜到的点就不是最优解了。
但是，我们会发现，如果\(ans=x\)，那么就一定是最优解了。因为这时\(ans\)已经是可能的最小值了。
同理，当队首的\(dist\)已经变成\(x+1\)，且\(ans=x+1\)，也就不用继续搜了。因为此时\(ans\)一定大于等于\(x+1\)。
关于\(vis\)数组的作用：
防止一条边被合并多次，因为我们实际上建立的双向边。
例如双向边\((a,b)\)：
先合并一次\(a->b\)，如果不打标记，还会访问到\(b->a\)，就得到了一个环，但是这是错误的。
代码和其他注意，见这个帖子。
标签：P8287,...,dist,R1,Flame,DAOI,答案,ans From： https://www.cnblogs.com/zhangchenxin/p/16878060.html