#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
//#define int long long
int parent[5005][5005];
vector <int> adj[5005],vec[5005];
void dfs(int x,int p,int root){
    parent[root][x]=p;
    for(auto u:adj[x]){
        if(u!=p){
            dfs(u,x,root);   
        }
    }
}
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> infect){
    for(auto u:R){
        adj[u.ff+1].pb(u.ss+1);
        adj[u.ss+1].pb(u.ff+1);
    }
    int m=t.size();
    int n=R.size()+1;
    vector <int> ans(m,0);
    for(int i=1;i<=n;i++){
        dfs(i,-1,i);
        
    }
    for(int i=0;i<m;i++){
        s[i]++;
        t[i]++;
        vec[s[i]].pb(i);
    }

    int k=n+1;
    while(k--){
        for(int i=1;i<=n;i++){
            bool mx=0;
            for(auto u:vec[i]){
                if(infect[u]==1){
                    mx=1;
                }
            }
            for(auto u:vec[i]){
                infect[u]=mx;
                if(infect[u]==1){
                    ans[u]++;
                }
            }

            vec[i].clear();
        }
        for(int i=0;i<m;i++){
            if(s[i]==-1)continue;
            s[i]=parent[t[i]][s[i]];
            if(s[i]!=-1)vec[s[i]].pb(i);
        }
    }
    return ans;
}
// signed main() {
//     int n, m;

//     std::cin >> n;
//     std::cin >> m;

//     std::vector<std::pair<int, int>> edges = {};
//     std::vector<long long> day;
//     std::vector<int> start;
//     std::vector<int> target;
//     std::vector<bool> infected;

//     for (int i = 0; i < n - 1; i++) {
//         int u, v;
//         std::cin >> u >> v;
//         edges.emplace_back(u, v);
//     }

//     for (int i = 0; i < m; i++) {
//         long long _d, _s, _t, _i;
//         std::cin >> _d >> _s >> _t >> _i;
//         day.push_back(_d);
//         start.push_back(_s);
//         target.push_back(_t);
//         infected.push_back(_i);
//     }

//     const auto ans = solve(edges, day, start, target, infected);
//     for (const auto it : ans) {
//         std::cout << it << std::endl;
//     }

//     return 0;
// }