#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;
bool pathbool;
vec pathans;
void path(int u, int p,int targ) {
	if (u == targ) {
		pathbool = 1;
		pathans.pshb(u);
		return;
	}
	for (auto &x : gp[u]) {
		if (x != p) {
			path(x, u,targ);
			if (pathbool) {
				pathans.pshb(u);
				return;
			}
		}
	}
}
vec solve(vector<pii> koxm, vec d, vec s, vec t, vec 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);
	}
	vector<vec> uxiner(m);
	for (int i = 0; i < m; i++) {
		pathans.clear();
		pathbool = 0;
		path(s[i], -1, t[i]);
		reverse(pathans.begin(), pathans.end());
		//cout << "??" << s[i] << " " << t[i] << endl;
		//for (int j = 0; j < pathans.sz; j++)cout << pathans[j] << " ";
		//cout << endl;
		uxiner[i] = pathans;
	}
	vec ans(m);
	for (int pah = 0; pah < n; pah++) {
		vec qaxaq(n);
		for (int j = 0; j < m; j++) {
			if (pah < uxiner[j].sz)qaxaq[uxiner[j][pah]] = max(h[j], qaxaq[uxiner[j][pah]]);
		}
		for (int j = 0; j < m; j++)if (pah < uxiner[j].sz)h[j] = max(h[j], qaxaq[uxiner[j][pah]]);
		for (int j = 0; j < m; j++)if (h[j] && pah<uxiner[j].sz)ans[j]++;
	}
	return ans;
}
