在这为期总共4周的ACM小学期里，qz被投喂了太多的解不出题的人，他感觉撑得慌。为了更好地消化，他决定在渡渡鸟王国进行一次惬意的旅行。
渡渡鸟王国有 座城市，城市的编号为 。其间有 条距离为 的单向道路，每条道路连接两座不同的城市。
在收到上面这条垃圾短信后，qz去JM旅行社预定了四倍满豪华旅行套餐。这意味着，qz需要选择 座互不相同的城市 ，并沿着 的路径完成他的旅行。不需要从 返回 。并且，在上述过程中，在从某一城市 前往另一城市 时，qz必须沿着任意一条从 到 的最短路径行走。也就是说，qz需要走过从 到 的最短路径、走过从 到 的最短路径、走过从 到 的最短路径，完成他的旅行。
为了尽可能地消化食物，qz希望选择城市 使得他在旅行中途经的总距离最长。注意，在旅行过程中可能可以重复访问某一城市，只要遵循前文所述的旅行规则即可。现在你需要告诉qz这个最长的旅行总距离是多少，否则qz不介意吃得更撑一点。