CF150E.Freezing with Style

This winter is so... well, you've got the idea :-) The Nvodsk road system can be represented as n junctions connected with n - 1 bidirectional roads so that there is a path between any two junctions. The organizers of some event want to choose a place to accommodate the participants (junction v), and the place to set up the contests (junction u). Besides, at the one hand, they want the participants to walk about the city and see the neighbourhood (that's why the distance between v and u should be no less than l). On the other hand, they don't want the participants to freeze (so the distance between v and u should be no more than r). Besides, for every street we know its beauty — some integer from 0 to 109. Your task is to choose the path that fits in the length limits and has the largest average beauty. We shall define the average beauty as a median of sequence of the beauties of all roads along the path.

We can put it more formally like that: let there be a path with the length k. Let a__i be a non-decreasing sequence that contains exactly k elements. Each number occurs there exactly the number of times a road with such beauty occurs along on path. We will represent the path median as number a⌊k / 2⌋, assuming that indexation starting from zero is used. ⌊x⌋ — is number х, rounded down to the nearest integer.

For example, if a = {0, 5, 12}, then the median equals to 5, and if a = {0, 5, 7, 12}, then the median is number 7.

It is guaranteed that there will be at least one path with the suitable quantity of roads.

这个冬天太……嗯，你懂的 :-) Nvodsk 的道路系统可以表示为 $ n $ 个路口，由 $ n-1 $ 条双向道路连接，使得任意两个路口之间都存在一条路径。某次活动的组织者希望选择一个供参与者住宿的地点（路口 $ v $）以及一个举办比赛的地点（路口 $ u $）。一方面，他们希望参与者在城市中步行游览、欣赏周边风景（因此 $ v $ 与 $ u $ 之间的距离应不小于 $ l $）；另一方面，他们又不希望参与者被冻着（因此 $ v $ 与 $ u $ 之间的距离应不大于 $ r $）。此外，每条道路都有其“美观度”——一个介于 $ 0 $ 到 $ 10^9 $ 之间的整数。你的任务是选出一条满足长度限制（即路径边数在 $ [l, r] $ 范围内）且平均美观度最大的路径。此处，“平均美观度”定义为该路径上所有道路美观度所构成序列的中位数。

更形式化地描述如下：设某条路径包含 $ k $ 条边。令 $ a_i $ 是一个严格非降序排列的序列，其中恰好包含 $ k $ 个元素；每个数值在序列中出现的次数，等于路径上具有该美观度的道路的数量。我们将该路径的中位数定义为 $ a_{\lfloor k/2 \rfloor} $，其中下标从 $ 0 $ 开始计数。$ \lfloor x \rfloor $ 表示将实数 $ x $ 向下取整（即不超过 $ x $ 的最大整数）。

例如，若 $ a = {0,,5,,12} $，则中位数为 $ 5 $；若 $ a = {0,,5,,7,,12} $，则中位数为 $ 7 $。

题目保证至少存在一条满足边数要求的路径。

The first line contains three integers n, l, r (1 ≤ l ≤ r < n ≤ 105).

Next n - 1 lines contain descriptions of roads of the Nvodsk, each line contains three integers a__i, b__i, c__i (1 ≤ a__i, b__i ≤ n, 0 ≤ c__i ≤ 109, a__i ≠ b__i) — junctions a__i and b__i are connected with a street whose beauty equals c__i.

第一行包含三个整数 $n$、$l$、$r$（$1 ≤ l ≤ r < n ≤ 10^5$）。

接下来 $n - 1$ 行描述了 Nvodsk 城市的道路，每行包含三个整数 $a_i$、$b_i$、$c_i$（$1 ≤ a_i, b_i ≤ n$，$0 ≤ c_i ≤ 10^9$，$a_i ≠ b_i$），表示路口 $a_i$ 与 $b_i$ 之间有一条街道，其美观度为 $c_i$。

Print two integers — numbers of the junctions, where to accommodate the participants and set up the contests, correspondingly. If there are multiple optimal variants, print any of them.

输出两个整数——分别为安排参赛者和设置比赛的路口编号。若存在多个最优方案，输出其中任意一个即可。

In the first sample all roads have the same beauty. That means that all paths of the positive length have the same median. Thus, any path with length from 3 to 4, inclusive will be valid for us.

In the second sample the city looks like that: 1 - 2 - 3 - 4 - 5 - 6. Two last roads are more valuable and we should choose any path that contains both of them and has the suitable length. It is either the path between 2 and 6 or the path between 3 and 6.

在第一个样例中，所有道路的美丽值都相同。这意味着所有长度为正的路径都具有相同的中位数。因此，任何长度在 $3$ 到 $4$（含端点）之间的路径对我们而言都是合法的。

在第二个样例中，城市结构如下：1 - 2 - 3 - 4 - 5 - 6。最后两条道路的价值更高，因此我们需要选择一条包含这两条道路且长度合适的路径。这样的路径要么是节点 $2$ 到 $6$ 之间的路径，要么是节点 $3$ 到 $6$ 之间的路径。