#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
#define x first
#define y second
const int MAX_N = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;
//
//
int n, k, tot;
int p, q, l1, l2, maxlen;
int d[MAX_N], pre[MAX_N];
int head[MAX_N];
bool vis[MAX_N], used[MAX_N];
struct node { int to, cost, next;} G[MAX_N];
inline void add(int u, int v, int w) {
    ++ tot;
    G[tot] = node{v, w, head[u]};
    head[u] = tot;
}
void dfs1(int x, int fa) {
    for(int i = head[x]; ~i; i = G[i].next) {
        int y = G[i].to, z = G[i].cost;
        if(y == fa) continue;
        d[y] = d[x] + z;
        dfs1(y, x);
    }
}
void dfs2(int x, int fa) {
    for(int i = head[x]; ~i; i = G[i].next) {
        int y = G[i].to, z = G[i].cost;
        if(y == fa) continue;
        d[y] = d[x] + z;
        pre[y] = x;
        dfs2(y, x);
    }
}
void dfs_tree_maxlen()