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

using namespace std;

typedef long long ll;

const int maxn=150005;
int n,m;
vector<int>v[maxn];

int currans;
void dfs(int node,int parent,int start,int finish,int depth)
{
    if(node==finish)
    {
        currans=depth;
        return;
    }

    for(int i : v[node])
    {
        if(i==parent)
            continue;
        dfs(i,node,start,finish,depth+1);
    }
}

std::vector<int> solve(std::vector<std::pair<int, int>> R,std::vector<long long> D,
                       std::vector<int> S,std::vector<int> T,std::vector<bool> I)
{
    n=R.size()+1;
    m=D.size();

    for(pair<int,int> i : R)
    {
        v[i.first].push_back(i.second);
        v[i.second].push_back(i.first);
    }

    vector<int>ret;
    for(int i=0;i<m;i++)
    {
        if(I[i]==0)
            ret.push_back(0);
        else
        {
            dfs(1,-1,S[i],T[i],1);
            ret.push_back(currans);
        }
    }

    return ret;
}
