#include "infection.h"
#include<iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <climits>
#define MAXN 150010
#define INF LLONG_MAX
using namespace std;
long long day[MAXN];
int st[MAXN];
int en[MAXN];
bool sick[MAXN];
vector<int> edges[MAXN];
vector<int> path[MAXN];
bool gone[MAXN];
bool dfs(int curr, int parent, const int init)
{
    if(curr==en[init]){path[init].push_back(curr);return 1;}
    for(int i=0;i<edges[curr].size();i++)
    {
        int now=edges[curr][i];
        if(now==parent)continue;
        if(dfs(now,curr,init))
        {
            path[init].push_back(curr);
            return 1;
        }
    }
    return 0;
}
int location[MAXN];
vector<int> solve(vector<pair<int, int>> R,vector<long long> D,vector<int> S,vector<int> T,vector<bool> I)
{
    for(int i=0;i<R.size();i++)
    {
        edges[R[i].first].push_back(R[i].second);
        edges[R[i].second].push_back(R[i].first);
    }
    int n=R.size()+1;
    int m=D.size();
    for(int i=0;i<m;i++)
    {
        day[i]=D[i];
        st[i]=S[i];
        en[i]=T[i];
        sick[i]=I[i];
        location[i]=S[i];
    }
    for(int i=0;i<m;i++)//get paths
    {
        dfs(st[i],-1,i);
        reverse(path[i].begin(),path[i].end());//redundant
    }

    /*for(int i=0;i<m;i++)
    {
        for(int j=0;j<path[i].size();j++)cout<<path[i][j]<<" ";
        cout<<"A\n";
    }*/

    vector<int> ans(m);

    for(int step=1;step<=n;step++)
    {
        vector<bool> spread;
        spread.clear();
        spread.resize(n);
        for(int i=0;i<m;i++)
        {
            if(gone[i])continue;
            if(sick[i]){ans[i]++;spread[location[i]]=1;}
        }
        for(int i=0;i<m;i++)
        {
            if(gone[i])continue;
            if(!sick[i])
            {
                if(spread[location[i]]){sick[i]=1;ans[i]++;}
            }
        }
        for(int i=0;i<m;i++)
        {
            if(gone[i])continue;
            if(step>=path[i].size())gone[i]=1;
            else location[i]=path[i][step];
        }
    }
    return ans;
}