#include "infection.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define F0R(i,a) FOR(i,0,a)
#define trav(a,x) for(auto &a : x)
#define sz(v) v.size()
#define mp make_pair
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vpi vector<pi>
#define vpl vector<pl>
#define vb vector<bool>
#define f first
#define s second
#define pb push_back

vvi g;


bool dfs(int u, int p, int e, vi& path){
    if(u == e){
        path.pb(u);
        return 1;
    }
    trav(v, g[u]){
        if(v == p)continue;
        bool f = dfs(v, u, e, path);
        if(f){
            path.pb(u);
            return 1;
        }
    }
    return 0;
}


vi solve(vpi R, vl D, vi S, vi T, vb I) {
    int n = sz(R) + 1, m = sz(D);
    g.clear();
    g.resize(n);
    F0R(i, n - 1){
        g[R[i].f].pb(R[i].s);
        g[R[i].s].pb(R[i].f);
    }
    vvi put(m);
    vi ans(m);
    F0R(i, m)if(I[i])ans[i] = max(ans[i], (int)sz(put[i]) - 0);
    F0R(i, m) dfs(S[i], -1, T[i], put[i]);
    F0R(i, n){
        vb in(n);
        F0R(j, m)if(sz(put[j]) > i)in[put[j][i]] = in[put[j][i]] | I[j];
        F0R(j, m)if(sz(put[j]) > i)I[j] = I[j] | in[put[j][i]];
        F0R(i, m)if(I[i])ans[i] = max(ans[i], (int)sz(put[i]) - i - 1);
    }
    return ans;
}
