#include "infection.h"
#include <bits/stdc++.h>
using namespace std;

const long long maxn=5005;
vector<int> pos,path[maxn],nei[maxn],anss;

bool dfs(long long curr, long long par, long long start, long long finish, long long ind){
    if(curr==finish){
        path[ind].push_back(curr);
        return true;
    }
    for(auto x: nei[curr]){
        if(x==par) continue;
        bool f=dfs(x,curr,start,finish,ind);
        if(f){
            path[ind].push_back(curr);
            return f;
        }
    }
    return false;
}

vector<int> solve(vector<pair<int,int>> r, vector<long long> d, vector<int> s, vector<int> t, vector<bool> inf){
    long long n=r.size()+1, m=s.size();
    pos=s;
    anss.assign(m,0);
    for(auto x: r){
        nei[x.first].push_back(x.second);
        nei[x.second].push_back(x.first);
    }
    for(long long i=0;i<m;i++){
        dfs(s[i],-1,s[i],t[i],i);
        //for(auto x: path[i]) cout<< x << " ";
        pos[i]=path[i].size();
        //cout<< endl;
    }
    for(long long day=0;day<n;day++){
        unordered_set<long long> curr_inf;
        for(long long j=0;j<m;j++){
            pos[j]--;
            if(pos[j]<0) continue;
            if(inf[j]){
                anss[j]++;
                curr_inf.insert(path[j][pos[j]]);
            }
        }
        for(auto x: curr_inf){
            for(long long j=0;j<m;j++){
                if(pos[j]<0) continue;
                if(path[j][pos[j]]==x && !inf[j]){
                    inf[j]=true;
                    anss[j]++;
                }
            }
        }
    }
    //for(auto x: anss) cout<< x << " ";
    return anss;
}
/*

9 4
0 1
1 2
2 3
3 4
4 5
3 6
6 7
6 8
0 0 5 1
0 5 7 0
0 7 8 0
0 0 1 0

*/
