#P18464. Graph Race

Graph Race

Graph Race

给定一张有 nn 个顶点、mm 条边的无权、无向、连通图。每个顶点 uu 都有两个整数 au,bua_u,b_u。

对于每个与顶点 11 之间有边相连的顶点 vv,求

$$\max_{\substack{1\le u\le n\\u\ne v}}\{a_u-b_u\cdot\operatorname{dist}(u,v)\},$$

其中 dist⁡(u,v)\operatorname{dist}(u,v) 表示图中 u,vu,v 之间的最短路径所包含的边数。

只有与顶点 11 直接相邻的顶点需要输出答案,但是最大值中的 uu 可以是图中的任意其它顶点,包括顶点 11;必须排除 u=vu=v。

输入格式

第一行包含两个整数 n,mn,m(2≤n≤3×1052\le n\le3\times10^5,1≤m≤3×1051\le m\le3\times10^5),分别表示顶点数和边数。

接下来 nn 行,第 uu 行包含两个整数 au,bua_u,b_u(0≤au,bu≤1090\le a_u,b_u\le10^9)。

接下来 mm 行,每行包含两个整数 u,vu,v(1≤u,v≤n1\le u,v\le n,u≠vu\ne v),表示一条连接 u,vu,v 的无向边。

保证图连通,且没有重边。输入只有一组图;顶点编号从 11 开始。bub_u 可以为 00。

输出格式

将所有与顶点 11 相邻的顶点 vv 按顶点编号从小到大排列,依次输出各自的上述最大值,每个答案占一行。

答案可能为负数;请使用足够宽的有符号整数类型。

完整原样例

5 4
0 0
1 1
1 1
5 1
100 40
4 1
1 2
1 3
4 5
3
3
60