#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool found;
void dfs(vector<int>& path, int s, vector<bool>& vis, vector<vector<int>>& a, int target){
    if(s == target){
        found = true;
        return;
    }
    vis[s] = true;
    for(int i = 0; i < a[s].size(); i++){
        if(vis[a[s][i]])continue;
        path.push_back(a[s][i]);
        dfs(path, a[s][i], vis, a, target);
        if(found)return;
        path.pop_back();
    }
}
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){
    int N = R.size() + 1, M = D.size();
    vector<int> ans(M, 0);
    vector<vector<int>> Path(M);
    vector<vector<int>> a(N);
    for(int i = 0; i < N - 1; i++){
        a[R[i].first].push_back(R[i].second);
        a[R[i].second].push_back(R[i].first);
    }

    vector<vector<int>> party(N);
    map<ll, map<int, vector<int>>> mp;
    vector<int> path;
    vector<bool> vis;
    int longestPath = 0;
    for(int i = 0; i < M; i++){
        path.clear();
        vis.assign(N, false);
        found = false;
        path.push_back(S[i]);
        vis[S[i]] = true;
        dfs(path, S[i], vis, a, T[i]);
        Path[i] = path;
        if(Path[i].size() > longestPath){
            longestPath = Path[i].size() ;
        }
        for(int j = 0; j < Path[i].size(); j++){
            mp[D[i] + j][Path[i][j]].push_back(i);
        }
        if(I[i])ans[i] = Path[i].size();
        //longestPath = max(longestPath, Path[i].size());
    }
    for(auto x : mp){
        for(auto y : x.second){
            bool sick = false;
            for(int i = 0; i < y.second.size(); i++){
                if(I[y.second[i]])sick = true;
            }
            if(sick){
                for(int i = 0; i < y.second.size(); i++){
                    if(ans[y.second[i]] == 0){

                        ans[y.second[i]] = (D[y.second[i]] + Path[y.second[i]].size()) - x.first;
                        I[y.second[i]] = true;

                    }

                }
            }
        }
    }
    return ans;
}

/*int main(){
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> r(n);
    vector<long long> d(m);
    vector<int> s(m);
    vector<int> t(m);
    vector<int> i(m);
    vector<bool> ist(m);
    for(int j = 0; j < n - 1; j++){
        cin >> r[j].first >> r[j].second;
    }
    for(int j = 0; j < m; j++){
        cin >> d[j];
        cin >> s[j] >> t[j];
        cin >> i[j];
        if(i[j] == 1){
            ist[j] = true;
        }else{
            ist[j] = false;
        }
    }
    vector<int> Ans = solve(r, d, s, t, ist);
    for(int j = 0; j < m; j++){
        cout << Ans[j] << " ";
    }
}*/
