给定一个包含 $n$ 个顶点和 $m$ 条边的无权无向连通图。每个顶点 $u$ 都被赋予了两个整数 $a_u$ 和 $b_u$。对于每个满足与顶点 $1$ 之间存在边的顶点 $v$，求：

$$\max_{u \neq v} \{a_u - b_u \cdot \text{dist}(u, v)\}$$

其中 $\text{dist}(u, v)$ 表示 $u$ 和 $v$ 之间的距离。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 3 \cdot 10^5$, $1 \le m \le 3 \cdot 10^5$)，分别表示图的顶点数和边数。

接下来的 $n$ 行，每行包含两个整数 $a_u$ 和 $b_u$ ($0 \le a_u, b_u \le 10^9$)。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u \neq v \le n$)，表示图中的边。保证图中不包含重边。

输出格式

按照 $v$ 的升序（其中 $v$ 为与顶点 $1$ 之间存在边的顶点），输出对应的 $\max_{u \neq v} \{a_u - b_u \cdot \text{dist}(u, v)\}$ 的值。

样例

样例输入 1

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

样例输出 1

3
3
60