#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define BIT(i) (1LL << i)
typedef long long ll;
const int MAXN = 1e5 + 7;
int par[MAXN][27], h[MAXN], n, k;
int root = 1;
vector <int> a[MAXN];
void dfs(int u, int p = 0){
	par[u][0] = p;
    h[u] = h[p] + 1;
    for(int i = 1; i <= 25; i++) par[u][i] = par[par[u][i - 1]][i - 1];
    for(auto v : a[u]) if(v != p) {
        dfs(v, u);
    }
}
 
int lca(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    int x = h[u] - h[v];
    for(int i = __lg(x); i >= 0; i--){
        if(x >= BIT(i)){
            x -= BIT(i);
            u = par[u][i];
        }
    }
    if(u == v) return u;
    for(int i = __lg(h[u]); i >= 0; i--){
        if(par[u][i] != par[v][i]){
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[v][0];
}
 
 
int main(){
    ios_base::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    while(cin >> n) {
    	if(n == 0) break;
    	root = 1;
    	for(int i=1; i<=n; i++) a[i].clear();
	    for(int i = 1; i <= n - 1; i++){
	        int x, y;
	        cin >> x >> y;
	        a[x].pb(y);
	        a[y].pb(x);
	    }
	    dfs(root);
	    // for(int i=0; i<=n; i++) cout << h[i] << " "; cout << "\n";
	    for(int i=1; i<=n; i++) assert(h[i] > 0);
	    cin >> k;
	    while(k--){
	        int u, v;
	    	char q;
	    	cin >> q;
	        if(q == '!') cin >> root;
	        else{
	            cin >> u >> v;
	            int uv = lca(u, v);
	            int ur = lca(u, root);
	            int vr = lca(v, root);
	            vector<int> ans = {uv, ur, vr};
	            sort(ans.begin(), ans.end(), [&](int a, int b) {return h[a] < h[b];});
	            cout << ans.back() << "\n";
	        }
	    }
    }
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgQklUKGkpICgxTEwgPDwgaSkKdHlwZWRlZiBsb25nIGxvbmcgbGw7CmNvbnN0IGludCBNQVhOID0gMWU1ICsgNzsKaW50IHBhcltNQVhOXVsyN10sIGhbTUFYTl0sIG4sIGs7CmludCByb290ID0gMTsKdmVjdG9yIDxpbnQ+IGFbTUFYTl07CnZvaWQgZGZzKGludCB1LCBpbnQgcCA9IDApewoJcGFyW3VdWzBdID0gcDsKICAgIGhbdV0gPSBoW3BdICsgMTsKICAgIGZvcihpbnQgaSA9IDE7IGkgPD0gMjU7IGkrKykgcGFyW3VdW2ldID0gcGFyW3Bhclt1XVtpIC0gMV1dW2kgLSAxXTsKICAgIGZvcihhdXRvIHYgOiBhW3VdKSBpZih2ICE9IHApIHsKICAgICAgICBkZnModiwgdSk7CiAgICB9Cn0KCmludCBsY2EoaW50IHUsIGludCB2KXsKICAgIGlmKGhbdV0gPCBoW3ZdKSBzd2FwKHUsIHYpOwogICAgaW50IHggPSBoW3VdIC0gaFt2XTsKICAgIGZvcihpbnQgaSA9IF9fbGcoeCk7IGkgPj0gMDsgaS0tKXsKICAgICAgICBpZih4ID49IEJJVChpKSl7CiAgICAgICAgICAgIHggLT0gQklUKGkpOwogICAgICAgICAgICB1ID0gcGFyW3VdW2ldOwogICAgICAgIH0KICAgIH0KICAgIGlmKHUgPT0gdikgcmV0dXJuIHU7CiAgICBmb3IoaW50IGkgPSBfX2xnKGhbdV0pOyBpID49IDA7IGktLSl7CiAgICAgICAgaWYocGFyW3VdW2ldICE9IHBhclt2XVtpXSl7CiAgICAgICAgICAgIHUgPSBwYXJbdV1baV07CiAgICAgICAgICAgIHYgPSBwYXJbdl1baV07CiAgICAgICAgfQogICAgfQogICAgcmV0dXJuIHBhclt2XVswXTsKfQoKCmludCBtYWluKCl7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOwogICAgY291dC50aWUoMCk7CiAgICBjaW4udGllKDApOwogICAgd2hpbGUoY2luID4+IG4pIHsKICAgIAlpZihuID09IDApIGJyZWFrOwogICAgCXJvb3QgPSAxOwogICAgCWZvcihpbnQgaT0xOyBpPD1uOyBpKyspIGFbaV0uY2xlYXIoKTsKCSAgICBmb3IoaW50IGkgPSAxOyBpIDw9IG4gLSAxOyBpKyspewoJICAgICAgICBpbnQgeCwgeTsKCSAgICAgICAgY2luID4+IHggPj4geTsKCSAgICAgICAgYVt4XS5wYih5KTsKCSAgICAgICAgYVt5XS5wYih4KTsKCSAgICB9CgkgICAgZGZzKHJvb3QpOwoJICAgIC8vIGZvcihpbnQgaT0wOyBpPD1uOyBpKyspIGNvdXQgPDwgaFtpXSA8PCAiICI7IGNvdXQgPDwgIlxuIjsKCSAgICBmb3IoaW50IGk9MTsgaTw9bjsgaSsrKSBhc3NlcnQoaFtpXSA+IDApOwoJICAgIGNpbiA+PiBrOwoJICAgIHdoaWxlKGstLSl7CgkgICAgICAgIGludCB1LCB2OwoJICAgIAljaGFyIHE7CgkgICAgCWNpbiA+PiBxOwoJICAgICAgICBpZihxID09ICchJykgY2luID4+IHJvb3Q7CgkgICAgICAgIGVsc2V7CgkgICAgICAgICAgICBjaW4gPj4gdSA+PiB2OwoJICAgICAgICAgICAgaW50IHV2ID0gbGNhKHUsIHYpOwoJICAgICAgICAgICAgaW50IHVyID0gbGNhKHUsIHJvb3QpOwoJICAgICAgICAgICAgaW50IHZyID0gbGNhKHYsIHJvb3QpOwoJICAgICAgICAgICAgdmVjdG9yPGludD4gYW5zID0ge3V2LCB1ciwgdnJ9OwoJICAgICAgICAgICAgc29ydChhbnMuYmVnaW4oKSwgYW5zLmVuZCgpLCBbJl0oaW50IGEsIGludCBiKSB7cmV0dXJuIGhbYV0gPCBoW2JdO30pOwoJICAgICAgICAgICAgY291dCA8PCBhbnMuYmFjaygpIDw8ICJcbiI7CgkgICAgICAgIH0KCSAgICB9CiAgICB9Cn0K

OQoxIDIKMSAzCjIgNAoyIDUKMyA2CjMgNwo2IDgKNiA5CjUKPyA0IDUKPyA1IDYKPyA4IDcKISA2Cj8gOCA3CjkKMSAyCjEgMwoyIDQKMiA1CjMgNgozIDcKNiA4CjYgOQo1Cj8gNCA1Cj8gNSA2Cj8gOCA3CiEgNgo/IDggNwo5CjEgMgoxIDMKMiA0CjIgNQozIDYKMyA3CjYgOAo2IDkKNQo/IDQgNQo/IDUgNgo/IDggNwohIDYKPyA4IDcKOQoxIDIKMSAzCjIgNAoyIDUKMyA2CjMgNwo2IDgKNiA5CjUKPyA0IDUKPyA1IDYKPyA4IDcKISA2Cj8gOCA3CjAK

9
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
5
? 4 5
? 5 6
? 8 7
! 6
? 8 7
9
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
5
? 4 5
? 5 6
? 8 7
! 6
? 8 7
9
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
5
? 4 5
? 5 6
? 8 7
! 6
? 8 7
9
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
5
? 4 5
? 5 6
? 8 7
! 6
? 8 7
0