Marty returned to the future and found Dr. Brown working on the innovative Kuantum resonance networks, a cutting-edge technology for communications based on the latest advances in quantum physics.
These networks are made up of $$$N$$$ Kuantum Processing Units (KPU), numbered from $$$1$$$ to $$$N$$$. The KPUs are connected in a tree structure, using bidirectional quantum cables. The KPU number $$$i$$$ operates at a specific frequency $$$F_i$$$.
According to the Kuantum protocol, the transmission of a message from a source KPU $$$X$$$ to a destination KPU $$$Y$$$ is divided into exactly three phases, which occur in the following order:
- Preparation: the message is transmitted instantaneously from $$$X$$$ to any KPU $$$w$$$ that operates at the same frequency as $$$X$$$, that is, with $$$F_X = F_w$$$.
- Transit: the message is transmitted from $$$w$$$ to any KPU $$$z$$$ such that $$$F_z = F_Y$$$, taking one unit of time for each cable used.
- Delivery: the message is transmitted instantaneously from $$$z$$$ to $$$Y$$$.
The following figure shows an example of transmission, in which a message from $$$X$$$ to $$$Y$$$ requires $$$4$$$ units of time. Remember that $$$F_X = F_w$$$ and $$$F_z = F_Y$$$.
Dr. Brown has finished building his first Kuantum network, and he needs to verify the efficiency of communication between different KPUs. As members of his team, you must write a program that can answer a series of queries. In each query, a source KPU $$$X$$$ and a destination KPU $$$Y$$$ are indicated, and you must calculate the minimum time required to transmit a message from $$$X$$$ to $$$Y$$$.
The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$), indicating the number of KPUs in the network. Each KPU is identified by a distinct integer between $$$1$$$ and $$$N$$$.
The second line contains $$$N$$$ integers $$${F_1}, {F_2}, \ldots, {F_N}$$$ ($$$1 \leq F_i \leq N$$$), indicating that the frequency of KPU $$$i$$$ is $$$F_i$$$.
Each of the following $$$N-1$$$ lines contains two integers $$$U$$$ and $$$V$$$ ($$$1 \leq U, V \leq N$$$ and $$$U \neq V$$$), indicating that there is a bidirectional cable connecting the KPUs $$$U$$$ and $$$V$$$. It is guaranteed that the network has a tree structure.
The next line contains an integer $$$C$$$ ($$$1 \leq C \leq 10^5$$$) representing the number of queries that need to be answered.
Each of the following $$$C$$$ lines describes a query with two integers $$$X$$$ and $$$Y$$$ ($$$1 \leq X, Y \leq N$$$), indicating respectively the source and destination KPUs for each query.
One line for each of the $$$C$$$ queries, with the corresponding answer, in the order in which the queries appear in the input.
9 1 2 2 3 3 4 4 4 4 1 7 1 3 4 8 7 2 5 6 9 2 8 9 6 2 7 1 1 2 1 1 3 1 4 4 5 4 3 5 3
0 1 1 4 0 2 2
In the second query of the example, the source KPU is $$$X=2$$$. During the preparation phase, the message is transmitted instantaneously to KPU $$$w=3$$$ since $$$F_2=F_3=2$$$. In the transit phase, it is transmitted to KPU $$$z=1$$$ in one unit of time (traversing the cable connecting KPUs $$$w=3$$$ and $$$z=1$$$). In the delivery phase, the message is transmitted instantaneously to the destination KPU $$$Y=1$$$, which in this case coincides with $$$z$$$. The total time is $$$1$$$ for this query.
In the fourth query, the optimal transmission is
which uses KPUs $$$w=1$$$ and $$$z=5$$$, taking $$$4$$$ units of time. A dashed arrow indicates instantaneous transmission in the preparation or delivery phases, while a solid arrow indicates the use of a cable in the transit phase. Note that it is not possible to transmit the message with
in $$$2$$$ units of time, since according to the three-phase protocol, the instantaneous transmission from KPU $$$7$$$ to KPU $$$8$$$ is not applicable in the transit phase.
