package LCA;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.BitSet;

public class AdaAndOrange_SPoj {
    public static void dfs(ArrayList<Integer> tree[],ArrayList<Integer> euler,int first[],
                           boolean visited[],int curr,int last[],int depth[]){
        visited[curr]=true;
        first[curr]=euler.size();
        last[curr]=euler.size();
        euler.add(curr);
        for(int j:tree[curr]){
            if(!visited[j]){
                depth[j]=depth[curr]+1;
                dfs(tree,euler,first,visited,j,last,depth);
                last[curr]=euler.size();
                euler.add(curr);
            }
        }
        return;
    }
    public static BitSet query(BitSet tree[],int s,int e,int l,int r,int treenode){
        if(s>r||e<l){
            return new BitSet();
        }
        if(s>=l&&e<=r){
            return tree[treenode];
        }
        int mid=(s+e)/2;
        BitSet left=(BitSet)query(tree,s,mid,l,r,2*treenode).clone();
        BitSet right=(BitSet)query(tree,mid+1,e,l,r,2*treenode+1).clone();
        left.or(right);
        return left;
    }
    public static void build(ArrayList<Integer> euler,int color[],BitSet tree[],int s,int e,int treenode){
//        System.out.println(s+" "+e+" "+treenode);
        if(s==e){
            tree[treenode]=new BitSet();
            tree[treenode].set(color[euler.get(s)]);
            return;
        }
        int mid=(s+e)/2;
        build(euler,color,tree,s,mid,2*treenode);
        build(euler,color,tree,mid+1,e,2*treenode+1);
        BitSet f=(BitSet)tree[2*treenode].clone();
        BitSet g=(BitSet)tree[2*treenode+1].clone();
        f.or(g);
        tree[treenode]=f;
        return;
    }
    public static Info2 query(Info2 tree[],int s,int e,int l,int r,int node){
        if(s>r||e<l){
            return new Info2(Integer.MAX_VALUE,0);
        }
        if(s>=l&&e<=r){
            return tree[node];
        }
        int mid=(s+e)/2;
        Info2 left=query(tree,s,mid,l,r,2*node);
        Info2 right=query(tree,mid+1,e,l,r,2*node+1);
        if(left.h<right.h){
            return left;
        }
        else{
            return right;
        }
    }
    public static void build2(int height[],Info2 segment[],int s,int e,int node,
                              ArrayList<Integer> euler){
        if(s==e){
            segment[node]=new Info2(height[euler.get(s)],euler.get(s));
            return;
        }
        int mid=(s+e)/2;
        build2(height,segment,s,mid,2*node,euler);
        build2(height,segment,mid+1,e,2*node+1,euler);
        if(segment[2*node].h<segment[2*node+1].h){
            segment[node]=segment[2*node];
        }
        else{
            segment[node]=segment[2*node+1];
        }
        return;
    }
    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder print=new StringBuilder();
        int test=Integer.parseInt(br.readLine());
        while(test--!=0){
            String line[]=br.readLine().split(" ");
            int n=Integer.parseInt(line[0]);
            int q=Integer.parseInt(line[1]);
            int root=Integer.parseInt(line[2]);
            int color[]=new int[n];
            line=br.readLine().split(" ");
            ArrayList<Integer> tree[]=new ArrayList[n];
            for(int i=0;i<n;i++){
                color[i]=Integer.parseInt(line[i]);
                tree[i]=new ArrayList<>();
            }
            for(int i=1;i<n;i++){
                line=br.readLine().split(" ");
                int x=Integer.parseInt(line[0]);
                int y=Integer.parseInt(line[1]);
                tree[x].add(y);
                tree[y].add(x);
            }
            ArrayList<Integer> eulerr=new ArrayList<>();
            int first[]=new int[n];
            int last[]=new int[n];
            int depth[]=new int[n];
            dfs(tree,eulerr,first,new boolean[n],root,last,depth);
//           
            BitSet segmenttree[]=new BitSet[4*eulerr.size()+4];
            Info2 mintree[]=new Info2[4*eulerr.size()+4];
            build(eulerr,color,segmenttree,0,eulerr.size()-1,1);
            build2(depth,mintree,0,eulerr.size()-1,1,eulerr);
            while(q--!=0){
                line=br.readLine().split(" ");
                int x=Integer.parseInt(line[0]);
                int y=Integer.parseInt(line[1]);
                Info2 lca=query(mintree,0,eulerr.size()-1,Math.min(first[x],first[y]),
                        Math.max(first[x],first[y]),1);
                BitSet ans=query(segmenttree,0,eulerr.size()-1,first[lca.index],
                        last[lca.index],1);
                print.append(ans.cardinality()+"\n");
            }
        }
        System.out.print(print.toString());
    }
}

class Info2{
    int h,index;
    public Info2(int h,int index){
        this.h=h;
        this.index=index;
    }

}

Won't the built time of sparse table hurt the complexity?