//#include "vision.h"
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 5e3 + 10;
int pr[N];
int par[N][N];
vector<vector<int>> g;
void dfs(int v, int p) {
    pr[v] = p;
    for (auto it : g[v]) {
        if (it == p) continue;
        dfs(it, v);
    }
}
bool inf[N];
vector<int> solve(vector<pair<int, int>> R, vector<long long> D, vector<int> S, vector<int> T, vector<bool> I) {
    int n = (int)R.size() + 1;
    int m = (int)D.size();
    vector<int> infdays(m);
    for (int i = 0; i < m; i++) {
        infdays[i] = 0;
    }
    g.clear();
    g.resize(n);
    for (int i = 0; i < n - 1; i++) {
        g[R[i].first].push_back(R[i].second);
        g[R[i].second].push_back(R[i].first);
    }
    for (int i = 0; i < n; i++) {
        dfs(i, i);
        for (int j = 0; j < n; j++) {
            par[j][i] = pr[j];
        }
    }
    vector<pair<int, int>> esim;
    for (int i = 0; i < m; i++) {
        esim.push_back({ D[i], i });
    }
    sort(esim.begin(), esim.end());
    vector<int> v;
    for (auto &it : esim) {
        v.push_back(it.second);
    }
    while (!v.empty()) {
        int i = 0;
        while (i != (int)v.size() && D[v[i]] == D[v[0]]) {
            i++;
        }
        for (int j = 0; j < i; j++) {
            if (I[v[j]]) inf[S[v[j]]] = true;
        }
        for (int j = 0; j < i; j++) {
            if (inf[S[v[j]]]) {
                I[v[j]] = true;
                infdays[v[j]]++;
            }
        }
        for (int j = 0; j < i; j++) {
            inf[S[v[j]]] = false;
        }
        int t = i;
        int j = 0;
        while (t--) {
            D[v[j]]++;
            if (S[v[j]] != T[v[j]]) { S[v[j]] = par[S[v[j]]][T[v[j]]]; j++; }
            else {
                v.erase(v.begin() + j);
            }
        }
    }
    return infdays;
}
/*
int main() {
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> R(n - 1);
    vector<long long> D(m);
    vector<int> S(m), T(m);
    vector<bool> I = { 1, 0, 0, 0, 0 };
    for (int i = 0; i < n - 1; i++) {
        cin >> R[i].first >> R[i].second;
    }
    for (int i = 0; i < m; i++) {
        cin >> D[i] >> S[i] >> T[i];
    }
    cout << "YEAH\n";
    vector<int> k = solve(R, D, S, T, I);
    for (int i = 0; i < k.size(); i++) {
        cout << k[i] << " ";
    }
    cout << "\n";
}*/