4117. 杨柳依依

单点时限: 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$ 表示最佳便利店位置,如有多个可输出任何一个

样例

Input
5 5
0 1
1 2
2 3
3 4
4 0
2
1 3
2 4
Output
2
Input
5 4
0 1
1 2
2 3
3 4
3
0 2
1 3
2 4
Output
2
Input
6 5
0 2
1 2
2 3
3 4
3 5
2
0 5
1 4
Output
2
Input
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
Output
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也是可以的

99 人解决,267 人已尝试。

126 份提交通过,共有 1258 份提交。

5.4 EMB 奖励。

创建: 3 月,2 周前.

修改: 3 月,2 周前.

最后提交: 5 天,15 小时前.

来源: N/A

题目标签