题目描述

在树之国，有 $n$ 个冰激凌摊位通过 $n-1$ 条双向道路连接成一棵树。每条道路 $i$ 有一个甜蜜值 $c_i$。国王宣布，找到一条长度在 $[l, r]$ 之间的路径，就能获得该路径上甜蜜值的中位数对应的免费冰激凌。

中位数定义为：若路径有 $k$ 条边，将边权排序后第 $\lceil \frac{k}{2} \rceil$ 大的值。例如路径边权为 $[5,3,4]$，中位数是 $4$。

请帮助小Z找到一条长度在 $[l, r]$ 之间的路径，使得该路径的中位数尽可能大。若有多条满足条件的路径，输出任意一条的起点和终点。

输入格式

第一行包含三个整数 $n$, $l$, $r$ ($1 \leq n \leq 10^5$, $1 \leq l \leq r \leq n-1$)，表示摊位数量和路径长度限制。

接下来 $n-1$ 行，每行三个整数 $a_i$, $b_i$, $c_i$，表示连接摊位 $a_i$ 和 $b_i$ 的道路甜蜜值 $c_i$ ($1 \leq c_i \leq 10^6$)。

输出格式

输出两个整数 $u$ 和 $v$，表示满足条件的路径的起点和终点。若有多个答案，输出任意一个。

5 3 4
1 2 1
2 3 2
3 4 3
4 5 4

1 5

样例分析

路径 $1-2-3-4-5$ 包含 $4$ 条边，边权为 $[1,2,3,4]$，中位数为 $3$。这是所有长度在 $3$ 到 $4$ 之间的路径中的最大可能中位数。

数据范围与提示

对于 $100\%$ 的数据，$1\leq n \leq 10^5$，$1\le c_i \leq 10^6$。