Kenan 为沿着巴库大街某一侧的建筑和天桥绘制了一张规划图。规划图中有
第
第
称某座天桥和某栋建筑相交,如果它们有某个公共的点。因此,一座天桥在它的两个端点处与两栋建筑相交,同时还可能在中间和其他建筑相交。
Kenan 想要找出从第
行人能够在任意交点从某座天桥走进某栋建筑,或者从某栋建筑走上某座天桥。如果两座天桥的端点之一在同一点上,行人也可以从其中一座天桥走上另一座天桥。
你的任务是帮助 Kenan 回答他的问题。
输入格式
第一行两个整数
以下
以下
最后一行,两个整数
输出格式
如果不存在一条合法的从
否则输出所有路径中长度最短的那一条。
样例一
plain
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5
output
27
explanation
样例二
plain
5 3
0 6
4 6
5 6
6 6
9 6
3 4 1
1 3 3
0 2 6
0 4
output
21
数据范围
测试包编号 | 限制与约定 | 分值 |
---|---|---|
10 | ||
每座天桥至多与 | 14 | |
15 | ||
18 | ||
无特殊约定 | 43 |
对于所有测试数据,满足
对于所有测试数据,满足
保证所有天桥仅可能在端点处相交。
时间限制:
空间限制: