#include "infection.h"
#include <vector>
#include <utility>
#include <bits/stdc++.h>
using namespace std;
const int cst=15*1e4+5,inf=1e7;
vector<int> mat[cst],rez,tras[cst];
int f[cst],f1[cst],timp[cst];
map<int,vector<int>> v1;
int dfs(int nod,int t)
{
    f1[nod]=1;
    if(nod==t)
    {
        rez.push_back(t);
        return 1;
    }
    for(auto vec:mat[nod])
    {
        if(f1[vec]==0)
        {
            int ok=dfs(vec,t);
            if(ok)
            {
                rez.push_back(nod);
                return ok+1;
            }
        }
    }
    return 0;
}
std::vector<int> solve(vector<pair<int, int>> R,vector<long long> D,vector<int> S,vector<int> T,vector<bool> I)
{
    int n=R.size()+1,m=S.size();
    for(auto it:R)
    {
        mat[it.first].push_back(it.second);
        mat[it.second].push_back(it.first);
    }
    for(int i=0; i<m; i++)
    {
        int s=S[i],t=T[i];
        rez.clear();
        timp[i]=dfs(s,t);
        tras[i]=rez;
        for(int i=0; i<=n; i++)
            f1[i]=0;
    }
    for(int i=0; i<m; i++)
        f[i]=timp[i];
    for(int i=0; i<m; i++)
        if(I[i]==1)
            f[i]=0;
    int active=m,d=0;
    while(active!=0)
    {
        v1.clear();
        for(int i=0; i<m; i++)
        {
            if(tras[i].size())
                v1[tras[i][tras[i].size()-1]].push_back(i);
        }
        for(auto itv:v1)
        {
            int ok=0;
            for(auto it:itv.second)
                if(I[it]==1)
                {
                    ok=1;
                    break;
                }
            if(ok==1)
                for(auto it:itv.second)
                {
                    f[it]=min(f[it],d);
                }
        }
        for(int i=0; i<m; i++)
        {
            if(tras[i].size())
            {
                tras[i].pop_back();
                if(tras[i].size()==0)
                    active--;
            }
        }
        d++;
    }
    rez.clear();
    for(int i=0; i<m; i++)
        rez.push_back(timp[i]-f[i]);
    for(int i=0; i<=n; i++)
        mat[i].clear();
    for(int i=0; i<=m; i++)
        f[i]=0;
    return rez;
}
