#include <bits/stdc++.h>
using namespace std;
vector <int> v[150005];
int d[150005], s[150005], t[150005], inf[150005];
int m, n;
int used[150005];
vector <int> party[5005][5005];
int dfs(int beg, int cnt, int p)
{
    used[beg] = 1;
    if(beg == t[p])
    {
        party[beg][cnt].push_back(p);
        return 1;
    }
    for(int i = 0; i < v[beg].size(); i++)
    {
        if(!used[v[beg][i]])
        {
            used[v[beg][i]] = 1;
            int c = dfs(v[beg][i], cnt+1, p);
            if(c == 1)
            {
                party[beg][cnt].push_back(p);
                return 1;
            }
        }
    }
    return 0;
}
std::vector<int> solve(std::vector<std::pair<int, int>> R, std::vector<long long> D, std::vector<int> S, std::vector<int> T, std::vector<bool> I)
{
    for(int i = 0; i < R.size(); i++)
    {
        v[R[i].first].push_back(R[i].second);
        v[R[i].second].push_back(R[i].first);
        n = max(n, R[i].first);
        n = max(n, R[i].second);
    }
    m = D.size();
    for(int i = 0; i < m; i++)
    {
        d[i] = D[i];
        s[i] = S[i];
        t[i] = T[i];
        inf[i] = I[i];
    }
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j <= n; j++)
            used[j] = 0;
        dfs(s[i], d[i], i);
    }
    vector <int> ans;
    for(int i = 0; i < m; i++)
        ans.push_back(0);
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            int c = 0;
            for(int k = 0; k < party[j][i].size(); k++)
            {
                if(inf[party[j][i][k]] == 1)c++;
            }
            if(c != 0)
            {
                for(int k = 0; k < party[j][i].size(); k++)
                {
                    if(inf[party[j][i][k]] == 0)
                    {
                        inf[party[j][i][k]] = 1;
                    }
                    if(inf[party[j][i][k]] == 1)ans[party[j][i][k]]++;
                }
            }
        }
    }
    return ans;
}
