Problem Description

You love strings a lot, so you decided to play the following game.

You have a tree T of A nodes. The tree is represented by a matrix B of dimensions (A — 1) * 2 such that there exist an edge between node B[i]|1| and B[i][2]

Each node is assigned a lowercase english character, which is represented by a string C of length A. Node is assigned character at position i of string C. You are given Q queries in the form of a matrix D of dimensions Q * 2 For each you query you will perform the following steps:

1. You will move from node p[i][1] to node D[i][2] using the shortest possible path.

2. Let V[1], V[2]...V[K] be the nodes visited in the corresponding order. Create a string $ such that length of S is equal to K and S[i]=c[v|i]]

3. Store string S in your bag.

Return the number of unique strings you would create.

Problem Constraints

I <= A <= 10 ^ 5

B is a matrix of dimensions (A — 1) * 2

Feel free to share aprroaches Thanks in Advance

1<=B[i][1] , B[i][2] <= A

length(C) = A

Conly contains lowercase english alphabets

1 <= Q <= 10 ^ 5

D is a matrix of dimensions Q * 2

1<=D[i][1],D[i][2]<=A