You are given a tree consisting of N nodes. You have to answer Q queries. The qth query consists of a node xq and a set of kq distinct nodes {v1,v2,…,vkq}. The answer to the qth query is the number of pairs (i,j) such that 1≤i<j≤kq and the node xq lies on the path between the nodes vi and vj.
Input format
Output format
For each query, print the answer in a separate line.
Constraints
2≤N≤2⋅1051≤Q≤2⋅1051≤Xi<Yi≤N1≤kq,xq,vq≤N∑kq≤3.5∗105
In the first query, the paths which contain node 3 are 1→5,1→8,2→5,2→8,5→8.
In the second query, the paths which contain node 2 are 2→4,2→6.