Problem B
Choir of Birds

In a large tree there is a choir of $N$ birds, one at each node. At any given node of the tree, the chirp from the bird at node $i$ can be heard with a sound volume of $floor(A_ i / (B_ i + d^2))$, where $A_ i$ and $B_ i$ are constants and $d$ is the distance to the bird when walking along the branches. At which node of the tree is the total volume the loudest?

Input

The first line contains a single number $N$ ($1 \le N \le 25000$), the number of nodes in the tree. The $N$ following lines contain two numbers each, $A_ i$ ($0 \le A_ i \le 25$) and $B_ i$ ($1 \le B_ i \le 25$), the constants for node $i$ ($0 \le i \le N-1$). The $N-1$ lines following that contain two numbers each, $p_ j$ and $q_ j$, the nodes connected by edge number $j$. The graph does not contain a cycle.

Output

A single number, the index of the node where the total volume is the loudest.

Test cases

There are three groups of test cases. To get the points for a group you need to succeed on all test cases in the group.

5
27 3
40 2
32 24
46 30
21 25
4 3
1 4
2 3
0 3

1

8
19 29
34 21
43 17
0 4
30 36
4 1
46 6
12 5
3 1
2 7
7 5
4 1
0 6
5 0
1 6

5