You are given an unweighted undirected connected graph with vertices and edges. Each vertex has two integers, a_u and b_u assigned to it. For each vertex such that there exists an edge between and find:
\max_{u \neq v} \{a_u - b_u \cdot \text{dist}(u,v)\}
where \text{dist}(u,v) denotes the distance between and .
The first line of the standard input contains two integers and (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 lines contain two integers each a_u and b_u (0 \leq a_u,b_u \leq 10^9).
The following lines contain two integers each and (1 \leq u \neq v \leq n), representing the edges of the graph. It is guaranteed that the graph doesn't contain multiple edges.
In ascending order with respect to such that there is an edge between and , print the value \max_{u \neq v} \{a_u - b_u \cdot \text{dist}(u,v)\}.
Example