宝宝，最著名的怪物猎人之一，醒来在赫尔滕市中心的怪物占主导地位。想不起发生了什么事，宝宝决定尽快逃离这个可怕的城市。尽管没有武器，他还是很幸运地把手放在右边口袋里的地图上，里面有可能帮助他找到出路的有价值的信息。

根据地图，赫尔亭市是由毫米无向路径连接的神经网络点组成。从11号现场开始，宝宝必须朝城市的任何一个 KK 出口逃跑，而第二个 KK 出口位于 ei 现场。

然而，宝宝想要逃脱并不容易，因为城里到处都是怪物！对于所有 1≤ i ≤ n 的怪物，di 都在第二个点附近徘徊，所以宝宝刚到达那个点，连接该点的 di 路线最多会被怪物堵住，宝宝无法通过。当宝宝离开第二个地点，怪物将回到他们的巢穴和堵塞的道路是明确的。

当然，如果宝宝回到原地，最多只能再次被怪物堵住。由于宝宝不知道哪条路会被堵住，所以请帮他计算一下，最坏的情况下，他能逃出城的最短时间。