Noel's Deliveries
By Gabriel Duarte, UNIFESO 
Brazil
By Gabriel Duarte, UNIFESO Brazil
Incredibly, Noel has not yet begun to make the gifts that will be delivered at Christmas. For him not to be late, a plan was created to expedite delivery and manufacturing.
Noel's plan is to choose two children (A and B) to be the first to receive gifts, but what he noticed is that on the way between child A's home and child B's home, he will eventually go through other children who also sent their letters with what they would like to win. So Noel has decided that he will deliver all the gifts of children who are between houses A and B in just one trip.
The delivery part is very simple for Noel, but he needs to optimize the purchase of raw materials to make all the presents, and this is where you will help.
You will be given the map with all the houses where deliveries will take place, which consists of N houses, with N - 1 links, having exactly one path between each of them, as Noel always travels by sleigh, all the links can be used in the two directions. After this Noel will ask several questions of type A B, and you must answer how many different gifts he will have to deliver on the way between house A and house B.
The first line contains two integers N and M (2 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁵), indicating the total number of houses and the total number of questions that Noel will ask.
In the next line will have the description of each gift that will be delivered in the houses. Each present will be a lowercase word containing a maximum of 20 characters. The present in position i, indicates what the child in house i wants to win.
Then follows N - 1 lines, containing two integers A and B (1 ≤ A, B ≤ N, A != B), indicating that there is a connection between houses A and B.
M lines follow with two integers A and B, representing Noel's question.
For each Noel question, you must print the different amount of gifts that will be delivered.
| Input Sample | Output Sample |
|
8 4 |
4 |