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


const int MAX_N = 5000;

vector <int> susNa[MAX_N];

int tim = 1;
int checked[MAX_N];
int dist[MAX_N];
int dfs (int start, int endd) {
    queue<int> toCheck;
    toCheck.push(start);
    dist[start] = 0;
    while(!toCheck.empty()) {
        int curr = toCheck.front();
        toCheck.pop();
        if (curr == endd) return dist[endd];
        if (checked[curr] == tim) continue;
        checked[curr] = tim;

        for (int i = 0; i < susNa[curr].size(); i ++) {
            int sus = susNa[curr][i];
            if (checked[sus] == tim) continue;
            dist[sus] = dist[curr] + 1;
            toCheck.push(sus);
        }
    }
    
    tim ++;
    return dist[endd];
}


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 < MAX_N; i ++) susNa[i].clear();
    for (int i = 0; i < R.size(); i ++) {
        auto curr = R[i];
        susNa[curr.first].push_back(curr.second);
        susNa[curr.second].push_back(curr.first);
    }

    int M = S.size();
    // cout << M << endl;
    
    vector <int> paths[MAX_N];
    vector <int> ans;
    

    for (int i = 0; i < M; i ++) {
        if (!I[i]) {
            ans.push_back(0);
            continue;
        }
        
        ans.push_back(dfs(S[i], T[i]) + 1);
        
    }

    return ans;
}
