Gem Collector on a Tree

You are given a tree with n cities numbered from 1 to n. The tree has n-1 undirected roads connecting the cities, ensuring that any city can be reached from any other city.

Each city hosts a market that sells a gem. There are m different gem types, numbered from 1 to m. The gem sold in city i is of type \(w_i\) (\(1 \le w_i \le m\)). Note that the same gem type may be sold in multiple cities.

K has a gem collector that collects gems following a fixed order defined by \(P_1, P_2, \ldots, P_c\) (all \(P_i\) are distinct). The collector must collect the gems in this precise order: it can only collect a gem of type \(P_1\) first. After it has collected a gem of type \(P_1\), it will then collect a gem of type \(P_2\), and so on.

When K visits a city, if the market sales gem type is the same as the current required gem type in the collector, then K will purchase one gem from that city and the collector will move on to the next required gem type. Otherwise, K will just pass through the city without buying anything.

You will be given q queries. Each query provides two cities \(s_i\) and \(t_i\). For each query, K starts at city \(s_i\) and travels along the unique shortest path to city \(t_i\). Determine the maximum number of gems K can collect along that path. Note that the collector is empty at the start of each query, and the gem available at the s_i and t_i cities can also be collected if they match the required order.

Input Format in brief:

• The first line contains three integers: \(n\), \(m\), and \(c\).
• The second line contains \(n\) integers: \(w_1, w_2, \ldots, w_n\), where \(w_i\) is the gem type sold in city \(i\).
• The third line contains \(c\) distinct integers: \(P_1, P_2, \ldots, P_c\) representing the collection order.
• The next \(n-1\) lines each contain two integers \(u\) and \(v\) denoting a road between cities u and v.
• The next line contains an integer \(q\), the number of queries.
• The following \(q\) lines each contain two integers \(s_i\) and \(t_i\>.

Output: For each query, output a single integer: the maximum number of gems that can be collected along the path from \(s_i\) to \(t_i\).

Note: All formulas are written in LaTeX format.

inputFormat

The input begins with a line containing three integers \(n\), \(m\), and \(c\).

The second line contains \(n\) integers \(w_1, w_2, \ldots, w_n\) (the gem type sold at each city).

The third line contains \(c\) distinct integers \(P_1, P_2, \ldots, P_c\) (the collection order).

Then, \(n-1\) lines follow, each with two integers \(u\) and \(v\) indicating a bidirectional road between cities \(u\) and \(v\).

The next line contains an integer \(q\), the number of queries.

Finally, \(q\) lines follow, each containing two integers \(s_i\) and \(t_i\) representing a query from city \(s_i\) to city \(t_i\>.

outputFormat

For each query, output on a new line a single integer representing the maximum number of gems that can be collected along the unique shortest path from \(s_i\) to \(t_i\>.

sample

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

3
3
2

</p>