Bessie正在农场上吃草，该农场由 $n$ 个由 $m$ 条双向道路连接的田野组成。她目前在第一个草地，将在一天结束时返回位于第 $n$ 个草地的家。Barns牛联邦已命令Farmer John安装一条额外的双向道路。农场有 $k$ 个特殊的草地，他决定在两个不同的特殊草地之间安装道路。他可以在已经有直接连接它们的两个特殊草地之间添加道路。道路添加后，Bessie将在从草地 $1$ 到草地 $n$ 的最短路径上返回家。由于Bessie需要更多的锻炼，Farmer John必须最大化这条最短路径的长度。请帮助他！
来源