#include<bits/stdc++.h>
#include "infection.h"
using namespace std;
    vector <int> v[150005];
    vector <bool> used;
    vector <int> path[150005];
    int kraj;
    vector <int> res;
void dfs (int s, int fin, int nach)
{
    //if (nach == 2) cout << "gurmi1" << endl;
    if (s == fin)
    {
        //if (nach == 2) cout << "gurmi2" << endl;
        kraj = fin;
        return;
    }
    used[s] = true;
    for (int i = 0; i < v[s].size(); i++)
    {
        //cout << "poli" << endl;
        //if (nach == 2) cout << "gurmi3" << endl;
        if (!used[v[s][i]] && kraj != fin)
        {
            //cout << "lilka" << endl;
            //if (nach == 2) cout << "gurmi4" << endl;
            path[nach].push_back(v[s][i]);
            dfs(v[s][i], fin, nach);
            //if (nach == 2) cout << "gurmi5" << endl;
            if (kraj == fin) return;
            //if (nach == 2) cout << "gurmi6" << endl;
            path[nach].pop_back();
        }
    }
}
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
)
{
    for (int i = 0; i < R.size(); i++)
    {
        int b = R[i].first;
        int e = R[i].second;
        v[b].push_back(e);
        v[e].push_back(b);
    }

    /*for (int i = 0; i < R.size(); i++)
    {
        for (int j = 0; j < v[i].size(); j++)
            cout << v[i][j] << " ";
        cout << endl;
    }*/
    for (int i = 0; i < D.size(); i++)
    {
        //cout << S[i] << " " << T[i] << " " << i << endl;
        used.clear();
        used.resize(R.size()+1, 0);
        path[i].push_back(S[i]);
        dfs(S[i], T[i], i);
        /*for (int j = 0; j < path[i].size(); j++)
        {
            cout << path[i][j] << " ";
        }
        cout << endl;*/
        kraj = -1;
    }
    res.resize(D.size(), 0);
    int maxi = -1;
    for (int i = 0; i < D.size(); i++)
    {
        int x = path[i].size();
        maxi = max(maxi, x);
    }
    /*for (int i = 0; i < D.size(); i++)
    {
        for (int j = 0; j < path[i].size(); j++)
        {
            cout << path[i][j] << " ";
        }
        cout << endl;
    }*/
    for (int i = 0; i <= maxi; i++)
    {
        for (int j = 0; j <= D.size(); j++)
        {
            for (int c = 0; c <= D.size(); c++)
            {
                if (j!=c && path[j][i] == path[c][i] && i <= path[j].size() && i <= path[c].size())
                {

                    if (I[j] == true && I[c] == false)
                    {
                        res[c] = i;
                        I[c] = true;
                        //cout << "den " << i << " " << j << " " << c << endl;
                    }
                    if (I[j] == false && I[c] == true)
                    {
                        res[j] = i;
                        I[j] = true;
                        //cout << "den " << i << " " << c << " " << j << endl;
                    }
                }
            }
        }
    }
    /*for (int i = 0; i < res.size(); i++)
    {
        cout << res[i] << " ";
    }
    cout << endl;*/
    for (int i = 0; i < res.size(); i++)
    {
        int dist = path[i].size();
        if (res[i] == 0 && I[i] == true) res[i] = dist;
        else if (I[i] == false) res[i] = 0;
        else res[i] = dist - res[i];
    }
    return {res};
}
