题目背景
译自 NOISG 2017 C.Hotspot。
题目描述
一个国家有 n 个城镇,这些城镇由 m 条长度相同的道路连接。
这个国家有 k 个公民。有趣的是,第 i 位公民的家和办公室位于两个不同的城镇 Ai 和 Bi。因此,第 i 个公民每天都会在 Ai 和 Bi 两个固定的城镇间往返。
为了节省时间,第 i 个公民将选择长度最短的路径。如果 Ai 和 Bi 间有多条最短路径,他 / 她将随机选择一条最短路径。第 i 个公民通过城镇 w 的期望为:
Ei(w)=S(Ai,Bi)Sw(Ai,Bi)
其中 S(u,v) 表示 u 和 v 间的最短路数量,Sw(u,v) 表示 u 和 v 间经过 w 的的最短路数量。
小 D 是这个国家的总统。他想了解公民的需求,于是想在国家的某一个城镇上设立一个会议办公室,因为这样他就可以会见尽可能多的公民。确切地说,他想将会议办公室设立在使 i=0∑k−1Ei(w) 最大的城镇 w。
你的任务是帮助小 D 找到符合要求的 w。当有多个符合要求的城镇 w 时,你可以输出其中的任何一个。
注意本题需要使用双精度浮点数。
输入格式
第一行两个正整数 n,m,分别表示城镇和道路的数量。
接下来 m 行,每行两个整数 u,v,表示城镇 u 和城镇 v 间有一条道路相连。
接下来一行包含一个正整数 k,表示公民的个数。
接下来 k 行,第 i 行两个整数 Ai,Bi,表示第 i 个公民的家和办公室的位置。
输出格式
一行一个整数表示使 i=0∑k−1Ei(w) 最大的城镇 w。如果有多个符合要求的解,输出其中的任何一个即可。
5 5
0 1
1 2
2 3
3 4
4 0
2
1 3
2 4
2
5 4
0 1
1 2
2 3
3 4
3
0 2
1 3
2 4
2
6 5
0 2
1 2
2 3
3 4
3 5
2
0 5
1 4
2
15 19
0 3
1 3
1 4
1 5
2 5
3 6
3 7
4 7
5 7
6 10
7 9
7 10
7 11
8 11
9 12
9 13
10 13
11 13
11 14
2
4 10
3 8
7
提示
样例解释
对于样例 1 和 3,显然选择城镇 3 也是正确的。
对于样例 4(如下图),在城镇 4 和城镇 10 之间只有一条长度为 2 的最短路径,即 4→7→10。此外,城镇 3 和城镇 8 之间只有一条长度为 3 的最短路径,即 3→7→11→8。
如果小 D 在城镇 7 建造会议办公室,那么 i=0∑k−1Ei(w)=2 最大。

数据范围
请注意本题时限为 2.5 秒。
本题采用 Subtask 捆绑测试。
Subtask |
分值 |
性质 |
1 |
4 |
图是一条链,且 n≤1000,m=n−1,k=1 |
2 |
5 |
图是一棵树,且 n≤1000,m=n−1,k=1 |
3 |
11 |
图是一条链,且 n≤1000,m=n−1,k≤200 |
4 |
18 |
图是一棵树,且 n≤1000,m=n−1,k≤200 |
5 |
26 |
n≤1000,m≤8000,k≤20 |
6 |
36 |
1≤n≤5000,1≤m≤4×104,1≤k≤2000 |
对于所有数据,保证 1≤n≤5000,1≤m≤4×104,1≤k≤2000,1≤u,v,Ai,Bi≤n,任何两个城镇之间的最短路不会超过 215 条。