POJ1330
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long LL;
const int MOD = + ;
const int INF = ;
const int N = + ;
const int LOG = ;
vector<int> G[N];
int parent[LOG][N];
int depth[N];
void dfs(int v, int p, int d) {
parent[][v] = p;
depth[v] = d;
for (int i = ; i < G[v].size(); i++)
if (G[v][i] != p) dfs(G[v][i], v, d + );
}
void init(int root, int V) {
dfs(root, -, );
for (int k = ; k + < LOG; k++) {
for (int v = ; v < V; v++) {
if (parent[k][v] < ) parent[k + ][v] = -;
else parent[k + ][v] = parent[k][parent[k][v]];
}
}
}
int lca(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
for (int k = ; k < LOG; k++) {
if ((depth[v] - depth[u]) >> k & )
v = parent[k][v];
}
if (u == v) return u;
for (int k = LOG - ; k >= ; k--) {
if (parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[][u];
}
bool isroot[N];
int main() {
#ifdef TYH
freopen("in.txt", "r", stdin);
#endif // TYH
int T, n;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
int a, b;
for(int i = ; i < n; i++) {
G[i].clear();
isroot[i] = true;
}
for(int i = ; i < n - ; i++) {
scanf("%d%d", &a, &b);
a--, b--;
G[a].push_back(b);
G[b].push_back(a);
isroot[b] = false;
}
int root = ;
for(int i = ;i<n;i++){
if(isroot[i] == true) root = i;
}
init(root, n);
scanf("%d%d", &a, &b);
a--, b--;
printf("%d\n", lca(a, b) + );
}
return ;
}