#include "infection.h"
#include <utility>
//#include <pch.h>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <ios>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <string>

#define FASTIO ios_base::sync_with_stdio(0);cin.tie(NULL);
#define vec vector<int>
#define pii pair<int,int>
#define vecl vector<long long>
#define sz size()
#define endl '\n'
#define pll pair<long,long>
#define ff first
#define ss second
#define pshb push_back
using ll = long long;


using namespace std;
vector<vec> gp;
vec tin, tout,par;
vector<vec> up;
int L;
int timer;
vec dist;
void dfs(int u, int p) {
	par[u] = p;
	tin[u] = ++timer;
	up[u][0] = p;
	for (int i = 1; i < L; i++)up[u][i] = up[up[u][i - 1]][i - 1];
	for (auto &x : gp[u]) {
		if (x != p) {
			dist[x] = dist[u] + 1;
			dfs(x, u);
		}
	}
	tout[u] = ++timer;
}
bool cnox(int u, int v) {
	return(tin[u] <= tin[v] && tout[u] >= tout[v]);
}
int lc(int u, int v) {
	if (cnox(u, v))return u;
	if (cnox(v, u))return v;
	for (int i = L - 1; i >= 0; i--) {
		if (!cnox(up[u][i], v))u = up[u][i];
	}
	return par[u];
}
vec solve(vector<pii> koxm, vecl d, vec s, vec t, vector<bool> h) {
	int n = koxm.sz + 1;
	int m = s.sz;
	gp = vector<vec>(n);
	for (int i = 0; i < n - 1; i++) {
		gp[koxm[i].ff].pshb(koxm[i].ss);
		gp[koxm[i].ss].pshb(koxm[i].ff);
	}
	par = tin = tout=vec(n);
	L = ceil(log2(n)) + 1;
	up = vector<vec>(n, vec(L));
	timer = 0;
	dist = vec(n);
	dfs(0,0);
	vec ans(m);
	for (int i = 0; i < m; i++) {
		if (h[i]) {
			int lca = lc(s[i], t[i]);
			int aranq = dist[s[i]] + dist[t[i]] - 2 * dist[lca];
			ans[i] = aranq + 1;
		}
	}
	return ans;
}
/*void solver() {
	int n, m; cin >> n >> m;
	vector<pii> koxm;
	vec s, t;
	vecl day;
	vector<bool> h;
	for (int i = 0; i < n - 1; i++) {
		int u, v; cin >> u >> v;
		koxm.pshb({ u,v });
	}
	for (int i = 0; i < m; i++) {
		ll a, b, c, d; cin >> a >> b >> c >> d;
		day.pshb(a);
		s.pshb(b);
		t.pshb(c);
		h.pshb(d);
	}
	vec ans=solve(koxm, day, s, t, h);
	for (int i = 0; i < ans.sz; i++)cout << ans[i] << " ";
}
int main() {
	FASTIO
	solver();
}*/