#include<iostream>
#include<vector>
using namespace std;
const int MAXN = 5000;
bool flag = false;
vector <int> graf[MAXN];
vector <int> put[MAXN];
void dfs(int tek, int index, int start, int finish){
    if(tek == finish){
        flag = true;
        put[index].push_back(finish);
        return ;
    }
    for(int i = 0; i < graf[tek].size(); i ++){
        dfs(graf[tek][i], index, start, finish);
        if(flag == true){
            put[index].push_back(graf[tek][i]);
            continue;
        }
    }
    return ;
}
vector<int> solve(vector<pair<int, int>> R,vector<long long> D,vector<int> S,vector<int> T,vector<bool> I){
    int maxG = 0;
    for(int i = 0; i < R.size(); i ++){
        int a = R[i].first;
        int b = R[i].second;
        graf[a].push_back(b);
        graf[b].push_back(a);
        maxG = max(maxG, a);
        maxG = max(maxG, b);
    }
    vector <int> zarazeni;
    vector <int> ans;
    int arr[MAXN];
    int M = D.size();

    int time = 0;
    for(int i = 0; i < M; i ++){
        flag = false;
        dfs(S[i], i, S[i], T[i]);
        put[i].push_back(S[i]);
        time = max(time, int(put[i].size()));
    }

    for(int i = 0; i < M; i ++){
        if(I[i]){
            zarazeni.push_back(i);
            arr[i] = put[i].size();
        }
    }
    bool flag2 = true;
    while(flag2){
        flag2 = false;
        for(int i = 0; i < zarazeni.size(); i ++){
            if(put[zarazeni[i]].size() - 1 - time >= 0){
                flag2 = true;
                for(int j = 0; j < M; j ++){
                    if(put[j].size() - 1 - time >= 0){
                        if(put[j][put[j].size() - 1 - time] == put[zarazeni[i]][put[zarazeni[i]].size() - 1 - time]){
                            I[j] = true;
                            zarazeni.push_back(j);
                            arr[j] = put[j].size() - time;
                        }
                    }
                }
            }
        }
    }
    for(int i = 0; i < M; i ++){
        ans.push_back(arr[i]);
    }
    return ans;
}