#include <bits/stdc++.h>
#include "infection.h"
using namespace std;
const int maxn=1e7;
vector<int>edges[maxn];
int used[maxn];
int m;
vector<int>ans;
int dist[maxn];
int bfs(int st, int ed)
{
    queue<int>q;
    q.push(st);
    used[st]=1;
    while(!q.empty())
    {
        int beg=q.front();
        q.pop();
        for(int nb: edges[beg])
        {
            if(!used[nb])
            {
                used[nb]=1;
                dist[nb]=dist[beg]+1;
                q.push(nb);
            }
        }
    }
    return dist[ed];
}
vector<int>solve(vector<pair<int, int>>r, vector<long long>d, vector<int>s, vector<int>t, vector<bool>I)
{
    int m=d.size();
    for(pair<int, int>j: r)
    {
        edges[j.first].push_back(j.second);
        edges[j.second].push_back(j.first);
    }
    for(int i=0;i<m;i++)
    {
        if(I[i]==0)
        {
            ans.push_back(bfs(s[i], t[i]));
        }
        else
        {
            ans.push_back(bfs(s[i], t[i]));
        }
    }
    return ans;
}
