const
tfi='';
tfo='';
var
fi,fo:Text;
ke,nx:array[-70000..70000] of longint;
num,thoat,hd:array[0..70000] of longint;
f:array[0..70000,0..20] of longint;
n,q,jmax,dem,dem1:longint;
t:array[0..3000000] of longint;
procedure nhap;
var i,j,u,v:longint;
begin
read(fi,n,q);
for i:=1 to n-1 do
begin
read(fi,u,v);
ke[i]:=v;
nx[i]:=hd[u];
hd[u]:=i;
ke[-i]:=u;
nx[-i]:=hd[v];
hd[v]:=-i;
end;
for j:=1 to 20 do if 1 shl j<=n then jmax:=j+1;
end;
procedure DFS(u:longint);
var j,v:longint;
begin
inc(dem);
num[u]:=dem;
for j:=1 to jmax do f[u,j]:=f[f[u,j-1],j-1];
j:=hd[u];
while j<>0 do
begin
v:=ke[j];
if f[v,0]=0 then
begin
f[v,0]:=u;
DFS(v);
end;
j:=nx[j];
end;
inc(dem1);
thoat[u]:=dem1;
end;
function cha(x,y:longint):boolean;
begin
cha:=(num[x]<=num[y]) and (thoat[y]<=thoat[x]);
end;
function lca(x,y:longint):longint;
var j:longint;
begin
if cha(x,y) then exit(x);
if cha(y,x) then exit(y);
for j:=jmax downto 0 do
if not cha(f[x,j],y) then x:=f[x,j];
exit(f[x,0]);
end;
procedure init(i,l,r:longint);
var mid:longint;
begin
if l=r then
begin
t[i]:=l;
exit;
end;
mid:=(l+r) div 2;
init(i*2,l,mid);
init(i*2+1,mid+1,r);
t[i]:=lca(t[i*2],t[i*2+1]);
end;
function get(i,l,r,u,v:longint):longint;
var mid:longint;
begin
if (l>v) or (r<u) then exit(u);
if (u<=l) and (r<=v) then exit(t[i]);
mid:=(l+r) div 2;
get:=lca(get(i*2,l,mid,u,v),get(i*2+1,mid+1,r,u,v));
end;
procedure xuli;
var i,u,v,pa,j:longint;
begin
f[1,0]:=1;
DFS(1);
init(1,1,n);
for i:=1 to q do
begin
read(fi,u,v);
writeln(fo,get(1,1,n,u,v));
end;
end;
begin
assign(fi,tfi);
assign(fo,tfo);
reset(fi);
rewrite(fo);
nhap;
xuli;
close(fo);
end.
Y29uc3QKICAgICAgICB0Zmk9Jyc7CiAgICAgICAgdGZvPScnOwogCnZhcgogICAgICAgIGZpLGZvOlRleHQ7CiAgICAgICAga2Usbng6YXJyYXlbLTcwMDAwLi43MDAwMF0gb2YgbG9uZ2ludDsKICAgICAgICBudW0sdGhvYXQsaGQ6YXJyYXlbMC4uNzAwMDBdIG9mIGxvbmdpbnQ7CiAgICAgICAgZjphcnJheVswLi43MDAwMCwwLi4yMF0gb2YgbG9uZ2ludDsKICAgICAgICBuLHEsam1heCxkZW0sZGVtMTpsb25naW50OwogICAgICAgIHQ6YXJyYXlbMC4uMzAwMDAwMF0gb2YgbG9uZ2ludDsKIApwcm9jZWR1cmUgbmhhcDsKICAgICAgICB2YXIgaSxqLHUsdjpsb25naW50OwogICAgICAgIGJlZ2luCiAgICAgICAgICAgICAgICByZWFkKGZpLG4scSk7CiAgICAgICAgICAgICAgICBmb3IgaTo9MSB0byBuLTEgZG8KICAgICAgICAgICAgICAgICAgICAgICAgYmVnaW4KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICByZWFkKGZpLHUsdik7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAga2VbaV06PXY7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbnhbaV06PWhkW3VdOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGhkW3VdOj1pOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGtlWy1pXTo9dTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBueFstaV06PWhkW3ZdOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGhkW3ZdOj0taTsKICAgICAgICAgICAgICAgICAgICAgICAgZW5kOwogICAgICAgICAgICAgICAgZm9yIGo6PTEgdG8gMjAgZG8gaWYgMSBzaGwgajw9biB0aGVuIGptYXg6PWorMTsKICAgICAgICBlbmQ7CiAKcHJvY2VkdXJlIERGUyh1OmxvbmdpbnQpOwogICAgICAgIHZhciBqLHY6bG9uZ2ludDsKICAgICAgICBiZWdpbgogICAgICAgICAgICAgICAgaW5jKGRlbSk7CiAgICAgICAgICAgICAgICBudW1bdV06PWRlbTsKICAgICAgICAgICAgICAgIGZvciBqOj0xIHRvIGptYXggZG8gZlt1LGpdOj1mW2ZbdSxqLTFdLGotMV07CiAgICAgICAgICAgICAgICBqOj1oZFt1XTsKICAgICAgICAgICAgICAgIHdoaWxlIGo8PjAgZG8KICAgICAgICAgICAgICAgICAgICAgICAgYmVnaW4KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB2Oj1rZVtqXTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZiBmW3YsMF09MCB0aGVuCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBiZWdpbgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBmW3YsMF06PXU7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIERGUyh2KTsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGVuZDsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBqOj1ueFtqXTsKICAgICAgICAgICAgICAgICAgICAgICAgZW5kOwogICAgICAgICAgICAgICAgaW5jKGRlbTEpOwogICAgICAgICAgICAgICAgdGhvYXRbdV06PWRlbTE7CiAgICAgICAgZW5kOwogCmZ1bmN0aW9uIGNoYSh4LHk6bG9uZ2ludCk6Ym9vbGVhbjsKICAgICAgICBiZWdpbgogICAgICAgICAgICBjaGE6PShudW1beF08PW51bVt5XSkgYW5kICh0aG9hdFt5XTw9dGhvYXRbeF0pOwogICAgICAgIGVuZDsKIApmdW5jdGlvbiBsY2EoeCx5OmxvbmdpbnQpOmxvbmdpbnQ7CiAgICAgICAgdmFyIGo6bG9uZ2ludDsKICAgICAgICBiZWdpbgogICAgICAgICAgICAgICAgaWYgY2hhKHgseSkgdGhlbiBleGl0KHgpOwogICAgICAgICAgICAgICAgaWYgY2hhKHkseCkgdGhlbiBleGl0KHkpOwogICAgICAgICAgICAgICAgZm9yIGo6PWptYXggZG93bnRvIDAgZG8KICAgICAgICAgICAgICAgICAgICAgICAgaWYgbm90IGNoYShmW3gsal0seSkgdGhlbiB4Oj1mW3gsal07CiAgICAgICAgICAgICAgICBleGl0KGZbeCwwXSk7CiAgICAgICAgZW5kOwogCnByb2NlZHVyZSBpbml0KGksbCxyOmxvbmdpbnQpOwogICAgICAgIHZhciBtaWQ6bG9uZ2ludDsKICAgICAgICBiZWdpbgogICAgICAgICAgICBpZiBsPXIgdGhlbgogICAgICAgICAgICAgICAgYmVnaW4KICAgICAgICAgICAgICAgICAgICAgICAgdFtpXTo9bDsKICAgICAgICAgICAgICAgICAgICAgICAgZXhpdDsKICAgICAgICAgICAgICAgIGVuZDsKICAgICAgICAgICAgbWlkOj0obCtyKSBkaXYgMjsKICAgICAgICAgICAgaW5pdChpKjIsbCxtaWQpOwogICAgICAgICAgICBpbml0KGkqMisxLG1pZCsxLHIpOwogICAgICAgICAgICB0W2ldOj1sY2EodFtpKjJdLHRbaSoyKzFdKTsKICAgICAgICBlbmQ7CiAKZnVuY3Rpb24gZ2V0KGksbCxyLHUsdjpsb25naW50KTpsb25naW50OwogICAgICAgIHZhciBtaWQ6bG9uZ2ludDsKICAgICAgICBiZWdpbgogICAgICAgICAgICAgICAgaWYgKGw+dikgb3IgKHI8dSkgdGhlbiBleGl0KHUpOwogICAgICAgICAgICAgICAgaWYgKHU8PWwpIGFuZCAocjw9dikgdGhlbiBleGl0KHRbaV0pOwogICAgICAgICAgICAgICAgbWlkOj0obCtyKSBkaXYgMjsKICAgICAgICAgICAgICAgIGdldDo9bGNhKGdldChpKjIsbCxtaWQsdSx2KSxnZXQoaSoyKzEsbWlkKzEscix1LHYpKTsKICAgICAgICBlbmQ7CiAKcHJvY2VkdXJlIHh1bGk7CiAgICAgICAgdmFyIGksdSx2LHBhLGo6bG9uZ2ludDsKICAgICAgICBiZWdpbgogICAgICAgICAgICAgICAgZlsxLDBdOj0xOwogICAgICAgICAgICAgICAgREZTKDEpOwogICAgICAgICAgICAgICAgaW5pdCgxLDEsbik7CiAgICAgICAgICAgICAgICBmb3IgaTo9MSB0byBxIGRvCiAgICAgICAgICAgICAgICAgICAgICAgIGJlZ2luCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcmVhZChmaSx1LHYpOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIHdyaXRlbG4oZm8sZ2V0KDEsMSxuLHUsdikpOwogICAgICAgICAgICAgICAgICAgICAgICBlbmQ7CiAKICAgICAgICBlbmQ7CiAKYmVnaW4KICAgICAgICBhc3NpZ24oZmksdGZpKTsKICAgICAgICBhc3NpZ24oZm8sdGZvKTsKICAgICAgICByZXNldChmaSk7CiAgICAgICAgcmV3cml0ZShmbyk7CiAgICAgICAgbmhhcDsKICAgICAgICB4dWxpOwogICAgICAgIGNsb3NlKGZvKTsKZW5kLg==