#include<bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const int bl = , N = 1e5 + ;

ull Num[];

vector<int> G[N];

int n, m, f, bbl, last;

ull Max;

int fa[N][], dep[N], mx[N], w[N], mark[N], top[N], mir[N];

int read() {

    int x = , f = ;

    char c = getchar();

    while(!isdigit(c)) {

        if(c == '-') {

            f = -;

        }

        c = getchar();

    }

    while(isdigit(c)) {

        x = x *  + c - '';

        c = getchar();

    }

    return x * f;

}

struct Bitset {

    int len;

    ull s[bl];

    void clear() {

        for(int i = ; i <= len; ++i) {

            s[i] = ;

        }

        len = ;

    }

    void operator |= (const Bitset &a) {

        len = max(len, a.len);

        for(int i = ; i <= len; ++i) {

            s[i] |= a.s[i];

        }

    }

    void operator |= (int b) {

        len = max(len, b >> );

        s[b >> ] |= 1LL << (b & );

    }

    int num() {

        int ret = ;

        for(int i = ; i <= len; ++i) {

            ret += Num[s[i] >> ] + Num[(s[i] >> ) & ] + Num[(s[i] >> ) & ] + Num[s[i] & ];

        }

        return ret;

    }

    int mex() {

        for(int i = ; i <= len; ++i) {

            if(s[i] != Max) {

                for(int j = ; j < ; ++j) {

                    if(!(s[i] & (1LL << j))) {

                        return i *  + j;

                    }

                }

            }

        }

    }

} b[][], ans;

void dfs(int u) {

    mx[u] = dep[u];

    for(int i = ; i < G[u].size(); ++i) {

        int v = G[u][i];

        if(v == fa[u][]) {

            continue;

        }

        fa[v][] = u;

        dep[v] = dep[u] + ;

        dfs(v);

        mx[u] = max(mx[u], mx[v]);

    }

    if(mx[u] - dep[u] >= bbl || u == ) {

        mark[u] = ++mark[];

        mir[mark[u]] = u;

        mx[u] = ;

    }

}

int lca(int u, int v) {

    if(dep[u] < dep[v]) {

        swap(u, v);

    }

    int d = dep[u] - dep[v];

    for(int i = ; i < ; ++i) {

        if(d & ( << i)) {

            u = fa[u][i];

        }

    }

    if(u == v) {

        return u;

    }

    for(int i = ; i >= ; --i) {

        if(fa[u][i] != fa[v][i]) {

            u = fa[u][i];

            v = fa[v][i];

        }

    }

    return fa[u][];

}

int main() {

    n = read();

    m = read();

    f = read();

    bbl = sqrt(n);

    for(int i = ; i < ; ++i) {

        Max |= 1LL << i;

    }

    for(int i = ; i < ; ++i) {

        for(int j = ; j < ; ++j) {

            if(i & ( << j)) {

                ++Num[i];

            }

        }

    }

    for(int i = ; i <= n; ++i) {

        w[i] = read();

    }

    for(int i = ; i < n; ++i) {

        int u = read(), v = read();

        G[u].push_back(v);

        G[v].push_back(u);

    }

    dep[] = ;

    dfs();

    for(int j = ; j <= ; ++j) {

        for(int i = ; i <= n; ++i) {

            fa[i][j] = fa[fa[i][j - ]][j - ];

        }

    }

    for(int i = ; i <= mark[]; ++i) {

        ans.clear();

        ans |= w[mir[i]];

        int x;

        b[i][i] |= w[mir[i]];

        for(x = fa[mir[i]][]; x; x = fa[x][]) {

            ans |= w[x];

            if(mark[x]) {

                b[i][mark[x]] = ans;

                if(!top[mir[i]]) {

                    top[mir[i]] = x;

                }

            }

        }

    }

    while(m--) {

        int a = read(), x, y, z;

        ans.clear();

        while(a--) {

            x = read();

            y = read();

            if(f) {

                x = x ^ last;

                y = y ^ last;

            }

            ans |= w[x];

            ans |= w[y];

            z = lca(x, y);

            for(; x && !mark[x] && dep[x] > z; x = fa[x][]) {

                ans |= w[x];

            }

            for(; y && !mark[y] && dep[y] > z; y = fa[y][]) {

                ans |= w[y];

            }

            int xx, yy;

            for(xx = x; dep[top[xx]] >= dep[z]; xx = top[xx]);

            for(yy = y; dep[top[yy]] >= dep[z]; yy = top[yy]);

            ans |= b[mark[x]][mark[xx]];

            ans |= b[mark[y]][mark[yy]];

            for(x = xx; dep[x] >= dep[z]; x = fa[x][]) {

                ans |= w[x];

            }

            for(y = yy; dep[y] >= dep[z]; y = fa[y][]) {

                ans |= w[y];

            }

        }

        int ta = ans.num(), tb = ans.mex();

        last = ta + tb;

        printf("%d %d\n", ta, tb);

    }

    return ;

}