bool M1; #define look_memory cerr< #include int _=1; using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair PII; #define pb push_back #define fi first #define se second #define rd read() #define Debug(x) (cerr< G[N]; void dfs(int u,int par){ dep[u]=dep[par]+1,fa[u][0]=par,sz[u]=1; for(int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int v:G[u]) if(v^par) dfs(v,u),sz[u]+=sz[v]; } int LCA(int u,int v){ if(dep[u]=dep[v]) u=fa[u][i]; if(u==v) return u; for(int i=19;~i;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } int up(int u,int x){ for(int i=19;~i;i--) if(x>>i&1) u=fa[u][i]; return u; } int solve(int u,int v){ if(dep[u]>1)-1)]-sz[up(v,(t>>1)-1)]; else return sz[up(u,t>>1)]-sz[up(u,(t>>1)-1)]; } } void Main(){ n=rd,q=rd; for(int i=1,u,v;i