Activity Monitoring on Tree Modules

A software platform consists of various modules arranged in a tree structure. Each module has a positive integer activity score and is connected to other modules by bidirectional edges so that there is exactly one unique path between any two modules.

Formally, let \( n \) be the number of modules, and each module \( i \) has a score \( s_i \). The modules are connected by \( n-1 \) roads, ensuring that the structure is a tree. You are given \( q \) queries; each query provides two modules \( u \) and \( v \), and your task is to determine the maximum activity score along the unique path from \( u \) to \( v \).

Example: If the activity scores are [1, 5, 3, 2, 4] and the edges are (1,2), (1,3), (2,4), (2,5), then for a query \( (1,4) \) the maximum score on the path is 5.

inputFormat

The input is given from standard input and has the following format:

• The first line contains two integers \( n \) and \( q \) — the number of modules and the number of queries.
• The second line contains \( n \) integers. The \( i \)th integer represents the activity score of module \( i \).
• The next \( n-1 \) lines each contain two integers \( u \) and \( v \) indicating that there is an edge connecting modules \( u \) and \( v \).
• The following \( q \) lines each contain two integers \( u \) and \( v \) representing a query for the maximum activity score on the path between modules \( u \) and \( v \).

outputFormat

For each query, output one line containing a single integer representing the maximum activity score on the unique path between the two specified modules.

## sample

5 3
1 5 3 2 4
1 2
1 3
2 4
2 5
1 4
4 5
3 4

5
5
5

</p>