// By rbtree (https://rbtree.dev)
#define AE3 n,nn,m,q,i,ii,j,bs,x,y,a[N],ta[N],la[M
#define AE2 1],l,f[N],dep[N],fa[N][21],dis[N][21];
#define AE1 // freopen("pictionary.out","w",stdout);
#define AE0 max(ans,max(dis[x][i],dis[y][i])),x
#define ADF // freopen("pictionary.in","r",stdin);
#define ADE x = (x << 1) + (x << 3) + ch - '0';
#define ADD max(ans,max(dis[x][0],dis[y][0]));
#define ADC print(lca_dis(read(),read()));
#define ADB add(x,y,i),add(y,x,i);
#define ADA max(ans,dis[x][i]),x
#define AD9 while(!isdigit(ch)){
#define AD8 while(isdigit(ch)){
#define AD7 c[N],b[N],bb[N];
#define AD6 if(dep[fa[x][i]]
#define AD5 putchar('\n');
#define AD4 if(ch == '-'){
#define AD3 ycl(v,x,w[i]);
#define AD2 1],dis[fa[x][i
#define AD1 putchar('-');
#define AD0 lca_dis(int1
#define ACF max(dis[x][i
#define ACE ___0xffff___
#define ACD 1],dis[x][i]
#define ACC while(q--){
#define ACB find(f[x]);
#define ACA ta[n],ta[n]
#define AC9 f,dis[x][0]
#define AC8 if(fa[x][i]
#define AC7 ycl(1,0,0);
#define AC6 getchar();
#define AC5 0x63467fa3
#define AC4 0x6347d15f
#define AC3 fa[x][i],y
#define AC2 print(int1
#define AC1 fa[y][i]){
#define AC0 fa[fa[x][i
#define ABF 1,fa[x][0]
#define ABE find(int1
#define ABD bs,go[bs]
#define ABC fa[y][i];
#define ABB fa[x][i];
#define ABA namespace
#define AB9 putchar(x
#define AB8 if(dep[x]
#define AB7 find(j),y
#define AB6 add(int1
#define AB5 read(),m
#define AB4 for(int1
#define AB3 dep[y]){
#define AB2 la[++bs]
#define AB1 read(),q
#define AB0 ycl(int1
#define AAF fa[x][i]
#define AAE 1],go[M
#define AAD if(f[x]
#define AAC read();
#define AAB read(){
#define AAA la[i]){
#define AA9 g,w[bs]
#define AA8 print(x
#define AA7 f,int1
#define AA6 dep[f]
#define AA5 dep[x]
#define AA4 return
#define AA3 go[i];
#define AA2 printf
#define AA1 find(j
#define AA0 n,int1
#define A9F 1],w[M
#define A9E x,int1
#define A9D g,int1
#define A9C ta[x];
#define A9B for(j
#define A9A i++){
#define A99 1]][i
#define A98 using
#define A97 i--){
#define A96 for(i
#define A95 0xb7
#define A94 0xb9
#define A93 0xbc
#define A92 0xc1
#define A91 0xc2
#define A90 0xc3
#define A8F 0xc6
#define A8E 0xc8
#define A8D 0xca
#define A8C 0xcb
#define A8B 0xcc
#define A8A 0xce
#define A89 0xcf
#define A88 0xd0
#define A87 0xd1
#define A86 0xd2
#define A85 0xd3
#define A84 0xd4
#define A83 0xd5
#define A82 0xd7
#define A81 0xda
#define A80 0xde
#define A7F 0xdf
#define A7E 0xe7
#define A7D 0xe8
#define A7C 0xeb
#define A7B 0xf7
#define A7A 0xf8
#define A79 0xfa
#define A78 0xfd
#define A77 1,nn
#define A76 10);
#define A75 1]);
#define A74 48);
#define A73 ans;
#define A72 bool
#define A71 0xc7
#define A70 char
#define A6F else
#define A6E f[i]
#define A6D f[x]
#define A6C f[y]
#define A6B if(v
#define A6A if(x
#define A69 ii);
#define A68 ii){
#define A67 int1
#define A66 main
#define A65 0x62
#define A64 "%s"
#define A63 "\n"
#define A62 0x20
#define A61 0x23
#define A60 0x2d
#define A5F 0x2e
#define A5E 0x2f
#define A5D 0x3a
#define A5C 0x61
#define A5B 0x63
#define A5A 0x64
#define A59 0x65
#define A58 0x66
#define A57 0x68
#define A56 0x6d
#define A55 std;
#define A54 0x6f
#define A53 0x70
#define A52 time
#define A51 0x73
#define A50 void
#define A4F 0x74
#define A4E 0x78
#define A4D 0xa7
#define A4C 0xa8
#define A4B 0xaa
#define A4A 0xb1
#define A49 0xb4
#define A48 0xb5
#define A47 d){
#define A46 -x;
#define A45 y,y
#define A44 0){
#define A43 -1;
#define A42 nn;
#define A41 int
#define A40 s){
#define A3F 9){
#define A3E 20;
#define A3D x,x
#define A3C 0,f
#define A3B 0xa
#define A3A ans
#define A39 ii;
#define A38 0x0
#define A37 f){
#define A36 x){
#define A35 y){
#define A34 (){
#define A33 i;
#define A32 if
#define A31 m;
#define A30 +=
#define A2F ^=
#define A2E <<
#define A2D d,
#define A2C ii
#define A2B d;
#define A2A &&
#define A29 n;
#define A28 ch
#define A27 f;
#define A26 ==
#define A25 1;
#define A24 0;
#define A23 s;
#define A22 >=
#define A21 x;
#define A20 10
#define A1F <=
#define A1E y;
#define A1D !=
#define A1C +
#define A1B *
#define A1A b
#define A19 a
#define A18 j
#define A17 <
#define A16 ;
#define A15 )
#define A14 (
#define A13 m
#define A12 %
#define A11 e
#define A10 n
#define AF f
#define AE ]
#define AD x
#define AC [
#define AB /
#define AA c
#define A9 v
#define A8 d
#define A7 -
#define A6 >
#define A5 ,
#define A4 =
#define A3 0
#define A2 i
#define A1 {
#define A0 }
#include <time.h>
#include<bits/stdc++.h>
#define N 100005
#define M 100004
#define int1 int
#define AE4 A98 ABA A55 A67 AE3 A2E AAE A2E A9F A2E
#define AE5 AE2 A72 AD7 A67 AAB A67 AD A4 A3C A4
#define AE6 A25 A70 A28 A4 AC6 AD9 AD4 AF A4 A43
#define AE7 A0 A28 A4 AC6 A0 AD8 ADE A28 A4 AC6
#define AE8 A0 AA4 AD A1B A27 A0 A50 AC2 A36 A6A
#define AE9 A17 A44 AD1 AD A4 A46 A0 A6A A6 A3F
#define AEA AA8 AB A76 A0 AB9 A12 A20 A1C A74 AA4
#define AEB A16 A0 A50 AB0 A9E AA7 A40 AA5 A4 AA6
#define AEC A1C ABF A4 AC9 A4 A23 A96 A4 A25 A2
#define AED A1F A3E A9A AAF A4 AC0 A7 A99 A7 ACD
#define AEE A4 ACF A7 AD2 A7 A99 A7 A75 A0 AB4
#define AEF A2 A4 A9C A33 A2 A4 AAA A67 A9 A4
#define AF0 AA3 A6B A1D A37 AD3 A0 A0 AA4 A16 A0
#define AF1 A67 AD0 A9E A35 A67 A3A A4 A24 AB8 A17
#define AF2 AB3 AD A2F A45 A2F A3D A2F A1E A0 A96
#define AF3 A4 A3E A2 A22 A24 A97 AD6 A22 AB3 A3A
#define AF4 A4 ADA A4 ABB A0 A0 A6A A26 A35 AA4
#define AF5 A73 A0 A96 A4 A3E A2 A22 A24 A97 AC8
#define AF6 A1D AC1 A3A A4 AE0 A4 AC3 A4 ABC A0
#define AF7 A0 AA4 ADD A0 A67 ABE A36 AAD A26 A36
#define AF8 AA4 A21 A0 AA4 A6D A4 ACB A0 A50 AB6
#define AF9 AA0 A9D A47 AB2 A4 ACA A4 ABD A4 AA9
#define AFA A4 A2B AA4 A16 A0 A41 ACE A34 ADF AE1
#define AFB A10 A4 AB5 A4 AB1 A4 AAC A96 A4 A25
#define AFC A2 A1F A29 A9A A6E A4 A33 A0 A96 A4
#define AFD A25 A2 A1F A31 A9A A2C A4 A13 A7 A2
#define AFE A1C A77 A4 A10 A7 A39 A9B A4 A39 A18
#define AFF A1F A42 A18 A30 A68 AD A4 AB7 A4 AA1
#define A100 A1C A69 A6A A1D A35 ADB A6C A4 A21 A0
#define A101 A0 A0 AC7 ACC ADC AD5 A0 AA4 A24 A0
#define A102 A41 A66 A14 A15 A1 A32 A14 A52 A14 A3
#define A103 A15 A6 AC5 A2A A52 A14 A3 A15 A17 AC4
#define A104 A15 A1 ACE A14 A15 A16 A0 A6F A1 A70
#define A105 A19 AC AE A4 A1 A14 A70 A15 A61 A5
#define A106 A14 A70 A15 A62 A5 A14 A70 A15 A49 A5
#define A107 A14 A70 A15 A79 A5 A14 A70 A15 A91 A5
#define A108 A14 A70 A15 A7C A5 A14 A70 A15 A8D A5
#define A109 A14 A70 A15 A4A A5 A14 A70 A15 A88 A5
#define A10A A14 A70 A15 A4D A5 A14 A70 A15 A94 A5
#define A10B A14 A70 A15 A78 A5 A14 A70 A15 A8F A5
#define A10C A14 A70 A15 A81 A5 A14 A70 A15 A86 A5
#define A10D A14 A70 A15 A87 A5 A14 A70 A15 A8A A5
#define A10E A14 A70 A15 A80 A5 A14 A70 A15 A95 A5
#define A10F A14 A70 A15 A4C A5 A14 A70 A15 A84 A5
#define A110 A14 A70 A15 A8C A5 A14 A70 A15 A88 A5
#define A111 A14 A70 A15 A88 A5 A14 A70 A15 A62 A5
#define A112 A14 A70 A15 A61 A5 A14 A70 A15 A38 A0
#define A113 A16 A70 A1A AC AE A4 A1 A14 A70 A15
#define A114 A61 A5 A14 A70 A15 A62 A5 A14 A70 A15
#define A115 A8E A5 A14 A70 A15 A7E A5 A14 A70 A15
#define A116 A88 A5 A14 A70 A15 A7D A5 A14 A70 A15
#define A117 A93 A5 A14 A70 A15 A8B A5 A14 A70 A15
#define A118 A88 A5 A14 A70 A15 A7A A5 A14 A70 A15
#define A119 A8D A5 A14 A70 A15 A94 A5 A14 A70 A15
#define A11A A85 A5 A14 A70 A15 A90 A5 A14 A70 A15
#define A11B A71 A5 A14 A70 A15 A7C A5 A14 A70 A15
#define A11C A92 A5 A14 A70 A15 A4B A5 A14 A70 A15
#define A11D A89 A5 A14 A70 A15 A48 A5 A14 A70 A15
#define A11E A82 A5 A14 A70 A15 A7B A5 A14 A70 A15
#define A11F A83 A5 A14 A70 A15 A7F A5 A14 A70 A15
#define A120 A62 A5 A14 A70 A15 A61 A5 A14 A70 A15
#define A121 A38 A0 A16 A70 AA AC AE A4 A1 A14
#define A131 A70 A15 A60 A5 A14 A70 A15 A60 A5 A14
#define A123 A70 A15 A62 A5 A14 A70 A15 A57 A5 A14
#define A124 A70 A15 A4F A5 A14 A70 A15 A4F A5 A14
#define A125 A70 A15 A53 A5 A14 A70 A15 A51 A5 A14
#define A126 A70 A15 A5D A5 A14 A70 A15 A5E A5 A14
#define A127 A70 A15 A5E A5 A14 A70 A15 A5B A5 A14
#define A128 A70 A15 A54 A5 A14 A70 A15 A5A A5 A14
#define A129 A70 A15 A59 A5 A14 A70 A15 A58 A5 A14
#define A12A A70 A15 A54 A5 A14 A70 A15 A4E A5 A14
#define A12B A70 A15 A5F A5 A14 A70 A15 A4F A5 A14
#define A12C A70 A15 A5C A5 A14 A70 A15 A54 A5 A14
#define A12D A70 A15 A65 A5 A14 A70 A15 A5C A5 A14
#define A12E A70 A15 A54 A5 A14 A70 A15 A5F A5 A14
#define A12F A70 A15 A5B A5 A14 A70 A15 A54 A5 A14
#define A130 A70 A15 A56 A5 A14 A70 A15 A62 A5 A14
#define A131 A70 A15 A60 A5 A14 A70 A15 A60 A5 A14
#define A132 A70 A15 A3B A5 A14 A70 A15 A38 A0 A16
#define A133 A70 A8 AC AE A4 A64 A16 A70 A11 AC
#define A134 AE A4 A63 A16 AA2 A14 A2D A19 A15 A16
#define A135 AA2 A14 A11 A15 A16 AA2 A14 A2D A1A A15
#define A136 A16 AA2 A14 A11 A15 A16 AA2 A14 A2D AA
#define A137 A15 A16 A0 AA4 A24 A0 
#define A138 AE4 AE5 AE6 AE7 AE8 AE9 AEA AEB AEC AED
#define A139 AEE AEF AF0 AF1 AF2 AF3 AF4 AF5 AF6 AF7
#define A13A AF8 AF9 AFA AFB AFC AFD AFE AFF A100 A101
#define A13B A102 A103 A104 A105 A106 A107 A108 A109 A10A A10B
#define A13C A10C A10D A10E A10F A110 A111 A112 A113 A114 A115
#define A13D A116 A117 A118 A119 A11A A11B A11C A11D A11E A11F
#define A13E A120 A121 A131 A123 A124 A125 A126 A127 A128 A129
#define A13F A12A A12B A12C A12D A12E A12F A130 A131 A132 A133
#define A140 A134 A135 A136 A137 
#define A141 A138 A139 A13A A13B A13C A13D A13E A13F A140 
#define A142(__FOX__) __FOX__
A142(A141)