新型冠状病毒引发肺炎疫情。在疫情爆发后,全国各地均出现了不同程度的物资紧缺情况,尤其是处于疫情中心的湖北省武汉市。为了驰援武汉抗击疫情,人们从全国各个城市调配了大量物资运往武汉,驰援抗疫。
为了简化问题,我们可以给不同的城市编上不同的编号,武汉市的编号为1。已知人们准备从个城市调配物资运往武汉,这些城市分别编号为2,3,4,……,
。在这
个城市中,某些城市之间建有高速公路直接把他们连在一起。已知这
个城市之间共建有
条高速公路,且每两个城市之间都存在若干条高速公路直接或间接地将它们连接起来。由于高速公路运力有限,在疫情期间,每条高速公路每天在同一个方向上最多只能运送1个单位的物资。但是我们可以认为城市的物资储存能力是无穷的,也就是说,如果物资从别处运抵某城市,但由于高速公路运力问题,这批物资无法立即运出,那么这批物资可以无限期地储存在当前的城市直到高速公路净空。
现在,给定每个城市中储备的物资的单位数量以及条高速公路的信息。你能编写一个程序计算,最少需要多少天时间才能够将所有城市中的物资全部运抵武汉(城市1)吗?
每个输入文件仅包含一组测试用例。
每个测试用例的第一行为一个整数
,表示城市的数量。(
)
每个测试用例的第二行为
个以空格分隔的整数,其中第
个整数
表示城市
中储备的物资的单位数量。(
)
每个测试用例接下来包含
行,每行包含两个整数
,表示城市
与城市
之间建有一条高速公路将它们直接相连。保证每两个城市之间最多只会存在一条高速公路。保证每两个城市均通过高速公路直接或间接地连接在一起。(
)
对于每个测试用例,输出一行一个整数表示至少需要多少天才能将所有城市中的所有物资运抵城市1。