#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
#include <iomanip>
#include <set>
#include <queue>
#include <stack>
#include <functional>
#define endl '\n'
#define int long long
#define si(x) (int)(x.size())


using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
int dfn[N], nw[N], w[N], son[N], fa[N], sz[N], h[N], up[N], idx;
bool st[N];
int dfa[N], n;
vector<PII> e[N];
struct dbq
{
    priority_queue<int> exi, out;
    void insert(int x)
    {
        exi.push(x);
    }
    void del(int x)
    {
        out.push(x);
    }
    int top()
    {
        while (!exi.empty() && !out.empty() && exi.top() == out.top()) exi.pop(), out.pop();
        if (exi.empty()) return 0;
        return exi.top();
    }
    int se_top()
    {
        int x = top();
        del(x);
        int res = top();
        insert(x);
        return res;
    }
    int size()
    {
        return si(exi) - si(out);
    }

}A[N], B[N], ans;//A[u]表示u中所有子树到u点分父节点的长度
//B[u]表示u所有儿子的A[son[u]]最大值集合，也包括他本身对自己的贡献0

struct NODE
{
    int l, r, sum;
    void init(int _l, int _r, int v)
    {
        l = _l, r = _r;
        sum = v;
    }
}tr[N << 2];

void pushup(int id)
{
    tr[id].sum = tr[id << 1].sum + tr[id << 1 | 1].sum;
}

void build(int id, int l, int r)
{
    if (l == r)
    {
        tr[id].init(l, r, nw[l]);
        return;
    }
    tr[id].init(l, r, 0);
    int mid = l + r >> 1;
    build(id << 1, l, mid), build(id << 1 | 1, mid + 1, r);
    pushup(id);
}

void modify(int id, int pos, int v)
{
    if (tr[id].l == tr[id].r)
    {
        tr[id].sum = v;
        return;
    }
    int mid = tr[id].l + tr[id].r >> 1;
    if (pos <= mid) modify(id << 1, pos, v);
    else modify(id << 1 | 1, pos, v);
    pushup(id);
}

int query(int id, int ql, int qr)
{
    if (tr[id].l == ql && tr[id].r == qr) return tr[id].sum;
    int mid = tr[id].l + tr[id].r >> 1;
    if (ql <= mid) return query(id << 1, ql, qr);
    else if (qr > mid) return query(id << 1 | 1, ql, qr);
    return query(id << 1, ql, mid) + query(id << 1 | 1, mid + 1, qr);
}

void dfs1(int u, int father, int dep)
{
    sz[u] = 1, h[u] = dep, fa[u] = father;
    for (auto [v, wg] : e[u])
    {
        if (v == father) continue;
        w[v] = wg;
        sz[u] += sz[v];
        if (sz[son[u]] < sz[v]) son[u] = v;
    }
}

void dfs2(int u, int t)
{
    dfn[u] = ++ idx, nw[idx] = w[u], up[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (auto [v, wg] : e[u])
    {
        if (v == son[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}

int dis(int u, int v)
{
    int res = 0;
    while (up[u] != up[v])
    {
        if (h[up[u]] < h[up[v]]) swap(u, v);
        res += query(1, dfn[up[u]], dfn[u]);
        u = fa[up[u]];
    }
    if (h[u] < h[v]) swap(u, v);
    if (dfn[v] + 1 <= dfn[u]) res += query(1, dfn[v] + 1, dfn[u]);
    return res;
}

int get_sz(int u, int father)
{
    if (st[u]) return 0;
    int sum = 1;
    for (auto [v, wg] : e[u])
    {
        if (v == father) continue;
        sum += get_sz(v, u);
    }
    return sum;
}

int get_wc(int u, int father, int tot, int &wc)
{
    if (st[u]) return 0;
    int sum = 1, mx = 0;
    for (auto [v, wg] : e[u])
    {
        if (v == father) continue;
        int t = get_wc(v, u, tot, wc);
        sum += t;
        mx = max(mx, t);
    }
    mx = max(mx, tot - sum);
    if (mx <= tot / 2) wc = u;
    return sum;
}

void divide(int u, int father)
{
    if (st[u]) return;
    int t = get_sz(u, father);
    get_wc(u, father, t, u);
    st[u] = true, dfa[u] = father;
    for (auto [v, wg] : e[u]) divide(v, u);
}

int count(int x)
{
    return B[x].top() + B[x].se_top();
}

void build_d_tree()
{
    for (int x = 1; x <= n; x ++)
    {
        for (int i = x; dfa[i]; i = dfa[i])
        {
            int d = dis(x, dfa[i]);
            A[i].insert(d);
        }
    }
    for (int i = 1; i <= n; i ++)
    {
        int p = dfa[i];
        B[i].insert(0);
        if (p) B[p].insert(A[i].top());
    }
    for (int i = 1; i <= n; i ++) if (B[i].size() > 1) ans.insert(count(i))
}

signed main()
{
#ifdef DEBUG
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(false); cin.tie(nullptr);
    return 0;
}