#include "infection.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define pii pair<int,int>
using namespace std;

const int N=5e3+5;
int n,m,st[N],en[N],inf[N],f[N][N];
vector<int> g[N],path[N];

int idx;
bool ff;

void dfs(int x, int p) {
	path[idx].pb(x);
	if (x==en[idx]) {
		ff=true; return;
	}
	for (auto y:g[x]) {
		if (y==p) continue;
		dfs(y,x);
		if (ff) return;
	}
	path[idx].pop_back();
}

vector<int> solve(vector<pair<int, int>> R,vector<long long> D,vector<int> S,vector<int> T,vector<bool> I) {
    n=R.size(); n++; m=D.size();
    int MX=max(n,m);
    for (int i=0; i<MX; i++) {
    	g[i].clear(); path[i].clear();
    	for (int j=0; j<MX; j++) {
    		f[i][j]=0;
		}
	}
	for (auto A:R) {
    	int a=A.f,b=A.s;
    	g[a].pb(b); g[b].pb(a);
	}
	for (int i=0; i<m; i++) {
		st[i]=S[i]; en[i]=T[i]; inf[i]=I[i]; idx=i; ff=false;
		dfs(st[i],st[i]);
//		cout<<"PATH I "<<i<<endl;
//		for (auto a:path[i]) cout<<a<<" "; cout<<endl;
	}
	vector<int> ans(m,0);
	for (int ind=0; ind<n; ind++) {
		for (int i=0; i<m; i++) {
			if (path[i].size()<=ind) continue;
			if (inf[i]==1) f[path[i][ind]][ind]=1;
		}
		for (int i=0; i<m; i++) {
			if (path[i].size()<=ind) continue;
			if (inf[i]==0) {
				if (f[path[i][ind]][ind]==1) {
					I[i]=1;
				}	
			}
			if (inf[i]==1) ans[i]++;
		}
	}
	return ans;
}