EOJ Monthly 2021.2 Sponsored by TuSimple
单点时限: 5.0 sec
内存限制: 512 MB
杨柳国的地图可以抽象成一张 $n$ 个点 $m$ 条边的无向连通图，每条边等长。图上有 $k$ 个人，其中第 $i$ 个人住在点 $a_i$，每天都要去 $b_i$ 上班。他会选择一条长度最短的路径，如果有多条，则等概率随机一条。
小 G 想找一个点开便利店。具体来说，她定义了 $E_i(w)$ 表示第 $i$ 个人经过点 $w$ 的概率，你需要帮助她找出 $\sum_{i=0}^{k-1} E_i(w)$ 最大的点 $w$。如有多个，可输出任意一个。
输入格式
第一行，两个正整数 $n$ 和 $m$
接下来 $m$ 行，每行两个整数 $u$ 和 $v$，表示一条边（节点编号从 $0$ 到 $n-1$）
接下来一行，一个正整数 $k$
接下来 $k$ 行，每行两个整数 $a_i$ 和 $b_i$，表示第 $i$ 个人的起点和终点
输出格式
一行，一个整数 $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
提示
样例4解释：
子任务 $1$，分值 $4$ 分，保证图是一条链，$n\le 1000$，$m=n-1$，$k=1$
子任务 $2$，分值 $5$ 分，保证图是一棵树，$n\le 1000$，$m=n-1$，，$k=1$
子任务 $3$，分值 $11$ 分，保证图是一条链，$n\le 1000$，$m=n-1$，$k\le 200$
子任务 $4$，分值 $18$ 分，保证图是一棵树，$n\le 1000$，$m=n-1$，$k\le 200$
子任务 $5$，分值 $26$ 分，保证 $n\le 1000$，$m\le 8000$，$k\le 20$
子任务 $6$，分值 $36$ 分，保证 $n\le 5000$，$m\le 40000$，$k\le 2000$
对所有数据，保证任意两点间最短路径数量不超过 $2^{15}$，注意本题需使用 double
样例1和3输出3也是可以的