#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll N = 2e5;
vector <vector <ll> > gr;
vector <vector <ll> > bin_up(N, vector <ll> (20));
vector <ll> dist(N);
ll n, m;
void dfs(ll v, ll ls, ll d){
    dist[v] = d;
    bin_up[v][0] = ls;
    for (int i = 1; i < 20; i++){
        if((1<<i) <= dist[v])
            bin_up[v][i] = bin_up[bin_up[v][i-1]][i-1];
    }
    for (auto u : gr[v]){
        if(u == ls) continue;
        dfs(u, v, d + 1);
    }
}
ll go(ll v, ll r){
    for (int i = 19; i > -1; i--){
        if(r >= (1<<i)){
            r -= (1<<i);
            v = bin_up[v][i];
        }
    }
    return v;
}
ll lca(ll a, ll b){
    if(dist[a] < dist[b])
        swap(a, b);
    a = go(a, dist[a] - dist[b]);
    if(a == b) return a;
    for (int i = 19; i > -1; i--){
        if(bin_up[a][i] != bin_up[b][i])
        {
            a = bin_up[a][i];
            b = bin_up[b][i];
        }
    }
    return bin_up[a][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){
   // return {6, 0, 4, 3, 0};
    n = R.size() + 1;
    m = D.size();
    gr.resize(n);
    for (int i = 0; i < n - 1; i++){
        ll a = R[i].first;
        ll b = R[i].second;
        gr[a].push_back(b);
        gr[b].push_back(a);
    }
    ll OK = 1;
    for (ll i = 0; i < m; i++){
        ll l = i * 1000000;
        if(D[i] != l)
          OK = 0;
        //cout << l << endl;
    }
    dfs(0, -1, 0);//cout << "good" << endl;
    if(OK == 1){
    vector <int> rec;
    for (int i = 0; i < m; i++){
        ll a = S[i];
        ll b = T[i];
        ll ans = dist[S[i]] + dist[T[i]];
        ll L = lca(a, b);
        ans -= 2 * dist[L];
        if(I[i] == 1)
        rec.push_back(ans + 1);
        else rec.push_back(0);
    }
    return rec;
    }

    vector <vector <ll> > cnt;
    vector <ll> rast(m);
    //map <ll,l>
    for (int i = 0; i < m; i++){
        vector <ll> way;
        ll a = S[i], b = T[i];
        ll L = lca(a, b);
        vector <ll> way1;
        while(true){
            way.push_back(a);
            if(a == L) break;
            a = bin_up[a][0];
        }
        while(b != L){
            way1.push_back(b);
            b = bin_up[b][0];
        }
        reverse(way1.begin(), way1.end());
        for (auto u : way1)
            way.push_back(u);
            ll ti = 0;
        for (auto u : way){
        cnt.push_back({D[i] + ti, u, i});
        ti++;
        }
        a = S[i];
        b = T[i];
        rast[i] = dist[a] + dist[b] - 2* dist[L] + 1;
    }
    sort(cnt.begin(), cnt.end());
    vector <int> rec(m, 0);
    vector <pair <int,int> > mb;
    for (int i = 0; i < cnt.size(); i++){
        cout << cnt[i][0] << " " << cnt[i][1] << endl;
        ll index = cnt[i][2];
        ll ver = cnt[i][1];
        ll ti = cnt[i][0];
        ll p = ti - D[index];
        int may = rast[index] - p;
        if(i == 0)
        mb.push_back({index, may});
        else{
        if(i > 0){
            if(cnt[i][0] == cnt[i - 1][0] && cnt[i][1] == cnt[i - 1][1])
                mb.push_back({index, may});
        else {
         /*   for (int j = 0; j < mb.size(); j++){
                cout << mb[j].first << " " << mb[j].second << endl;
            }
            cout << endl;*/
            ll ok = 0;
            for (int j = 0; j < mb.size(); j++)
            {
                ll w = mb[j].first;
                if(I[w] == 1)
                    ok = 1;
            }
            if(ok == 1){
                for (int j = 0; j < mb.size(); j++){
                    ll w = mb[j].first;
                    rec[w] = max(rec[w], mb[j].second);
                    I[w] = 1;
                }
            }
            mb.clear();
            mb.push_back({index, may});
        }
        }
        }

    }
    ll ok = 0;
    for (int j = 0; j < mb.size(); j++)
        {
            ll w = mb[j].first;
            if(I[w] == 1)
                ok = 1;
        }
        if(ok == 1){
            for (int j = 0; j < mb.size(); j++){
                ll w = mb[j].first;
                rec[w] = max(rec[w], mb[j].second);
                I[w] = 1;
            }
        }
    return rec;
}