#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair <int, int>
#define ld long double
#define ins insert
#define pb push_back
using namespace std;

const int N = 2e5 + 5;
const ll inf = 1e13;

vector <int> g[N];
int pr[N], tin[N], tout[N];
int timer;
void dfs(int v, int p = 0)
{
    timer++;
    tin[v] = timer;
    pr[v] = p;
    for (auto to: g[v]) if (to != p)
    {
        dfs(to, v);
    }
    timer++;
    tout[v] = timer;
}

deque <int> way[N];

bool upper(int v, int u)
{
    return tin[v] <= tin[u] && tout[u] <= tout[v];
}

ll dl[N];

void build(int v, int u, int i)
{
    vector <int> a, b;
    while (!upper(v, u))
    {
        a.pb(v);
        v = pr[v];
    }
    while (!upper(u, v))
    {
        b.pb(u);
        u = pr[u];
    }
    b.pb(u);
    for (auto to: a) way[i].pb(to);
    reverse(b.begin(), b.end());
    for (auto to: b) way[i].pb(to);
    dl[i] = way[i].size();
    return;
}

ll lst[N];
ll whn[N];
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();
    for (auto to: R) {g[to.F + 1].pb(to.S + 1); g[to.S + 1].pb(to.F + 1);}
    dfs(1);
    for (int i = 1; i <= n; i++) lst[i] = -1;
    for (int i = 0; i < m; i++)
    {
        build(S[i] + 1, T[i] + 1, i + 1);
    }
    priority_queue <pair <ll, pii>, vector <pair <ll, pii>>, greater <pair <ll, pii>>> q;
    for (int i = 0; i < m; i++)
    {
        q.push({D[i], {1-I[i], i + 1}});
        if (!I[i]) whn[i + 1] = inf;
    }
    while (q.size())
    {
        auto to = q.top();
        q.pop();
        ll tim = to.F;
        int fl = 1 - to.S.F, id = to.S.S;
        int v = way[id].front();
//        cerr << "!!! " << tim << ' ' << fl << ' ' << id << ' ' << v << ' ' << way[id].size() << endl;
        if (fl) lst[v] = max(lst[v], tim);
        else if (lst[v] == tim)
        {
            whn[id] = min(whn[id], tim);
            fl = 1;
        }
        way[id].pop_front();
        if (!way[id].size()) continue;
//        int nw = way[id].front();
        q.push({tim + 1, {1 - fl, id}});
    }
    vector <int> ans;
    for (int i = 1; i <= m; i++)
    {
        ans.pb(max(0ll, min(dl[i] + D[i - 1] - whn[i], dl[i])));
    }
    return ans;
}


//int32_t main()
//{
//    int n, m;
//    cin >> n >> m;
//    vector <pii> r;
//    vector <int> s, t;
//    vector <bool> ii;
//    vector <ll> d;
//    for (int i = 1; i < n; i++)
//    {
//        int v, u;
//        cin >> v >> u;
//        r.pb({v, u});
//    }
//    for (int i = 1; i <= m; i++)
//    {
//        int D, S, T, I;
//        cin >> D >> S >> T >> I;
//        d.pb(D);
//        s.pb(S);
//        t.pb(T);
//        ii.pb(I);
//    }
//    vector <int> ans = solve(r, d,s,t,ii);
//    for (auto to: ans) cout << to << endl;
//    return 0;
//}
