Your grandparents have decided to come visit you for Christmas! However, you notice that they are squinting as they look at your Christmas tree!
Being the computer science nerd that you are, your Christmas tree is a tree with nodes, the of which has a light with a brightness of . The similarity of a path is the minimum non-negative difference between the brightnesses of any two distinct nodes on the path. Given that your grandparents look at paths, can you tell them what the similarity of each path is?
For all subtasks:
Subtask 1 [10%]
Subtask 2 [10%]
Subtask 3 [80%]
The first line of input will contain two space-separated integers, and .
The next line of input will contain space-separated integers, .
The next lines will contain two space-separated integers, and , indicating that there is an edge between nodes and .
The next lines will each contain two space-separated integers, and , indicating that your grandparents look at the path to .
Output lines. The line should contain a single integer: the similarity of the path from to .
5 3 1 8 7 5 6 2 4 4 1 3 1 1 5 2 3 4 3 5 2
1 2 1