G. Graph Race
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an unweighted undirected connected graph with $$$n$$$ vertices and $$$m$$$ edges. Each vertex $$$u$$$ has two integers, $$$a_u$$$ and $$$b_u$$$ assigned to it. For each vertex $$$v$$$ such that there exists an edge between $$$1$$$ and $$$v$$$ find:

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

where $$$\text{dist}(u,v)$$$ denotes the distance between $$$u$$$ and $$$v$$$.

Input

The first line of the standard input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq m \leq 3 \cdot 10^5$$$), respectively denoting the number of vertices of a graph and the number of its edges.

The following $$$n$$$ lines contain two integers each $$$a_u$$$ and $$$b_u$$$ ($$$0 \leq a_u,b_u \leq 10^9$$$).

The following $$$m$$$ lines contain two integers each $$$u$$$ and $$$v$$$ ($$$1 \leq u \neq v \leq n$$$), representing the edges of the graph. It is guaranteed that the graph doesn't contain multiple edges.

Output

In ascending order with respect to $$$v$$$ such that there is an edge between $$$1$$$ and $$$v$$$, print the value $$$\max_{u \neq v} \{a_u - b_u \cdot \text{dist}(u,v)\}$$$.

Example
Input
5 4
0 0
1 1
1 1
5 1
100 40
4 1
1 2
1 3
4 5
Output
3
3
60