問題文
Atcoder在运输公司中,N存在一个工厂。
217X年,在这家公司,1只有一个困扰,那就是公司之间不存在道路相连。
运输公司社长「这是大问题!!不马上修的话就糟了!!」
所以现在是时候开始计划了。
该公司涉及运输,因此产品必须快速地从农村运输到城市,从城市运输到农村。因此,如果您为您的公司创建专用路径,您将能够处理许多订单。
但是,需要在以下条件下创建道路。
- 道路应笔直,尽可能提高运输卡车的限速。
- 除工厂外,道路不应相交,因为分级交叉口会显着增加成本。
- 除了提高所有专用道路的速度限制外,我们希望尽快将车辆运送到目标公司。 我会修尽可能多的路。
- 假设有道路连接工厂。
然而,该公司不知道如何得出最优解。
公司要求你,一个优秀的程序员,找到最优的解决方案。找出可以修建的最大道路数量。
但是,必须严格遵守问题文本中的条件。
注:题文中的217X年是超时空世界的时间。这里的时间可以被认为是现在。