这个冬天是如此......好吧,你已经明白了:-) Nvodsk 道路系统可以表示为与 n - 1 条双向道路连接的 n 个交叉路口,因此任意两个交叉路口之间都有一条路径。一些活动的组织者想要选择一个容纳参与者的地方(v 路口),以及举办比赛的地方(u 路口)。此外,一方面,他们希望参与者在城市中漫步并看看邻居(这就是为什么 v 和 u 之间的距离应该不小于 l)。另一方面,他们不希望参与者冻结(因此 v 和 u 之间的距离不应大于 r)。此外,对于每条街道,我们都知道它的美丽程度 - 0 到 109 之间的某个整数。您的任务是选择符合长度限制且具有最大平均美丽程度的路径。我们将平均美丽度定义为沿途所有道路的美丽度序列的中位数。
我们可以更正式地说:设一条长度为k的路径。令 ai 为恰好包含 k 个元素的非递减序列。每个数字出现的次数恰好是路径上出现如此美丽的道路的次数。我们将路径中位数表示为数字 a⌊k / 2⌋,假设使用从零开始的索引。 ⌊x⌋ — 是数字 х,向下舍入到最接近的整数。
例如,如果 a = {0, 5, 12},则中位数等于 5,如果 a = {0, 5, 7, 12},则中位数为数字 7。
保证至少有一条具有适当数量道路的路径。
输入
第一行包含三个整数 n、l、r (1 ≤ l ≤ r < n ≤ 105)。
接下来 n - 1 行包含 Nvodsk 道路的描述,每行包含三个整数 ai, bi, ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 109, ai ≠ bi) — 交叉点 ai 和 bi 与一条美丽等于 ci 的街道相连。
输出
打印两个整数 - 路口的数量,相应地容纳参与者并设置比赛。如果有多个最佳变体,请打印其中任何一个。
示例
输入 #1
6 3 4 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1
输出 #1
4 1
输入 #2
6 3 4 1 2 1 2 3 1 3 4 1 4 5 2 5 6 2
输出 #2
6 3
输入 #3
5 1 4 1 2 1 1 3 4 3 4 7 3 5 2
输出 #3
4 3
输入#4
8 3 6 1 2 9 2 3 7 3 4 7 4 5 8 5 8 2 3 6 3 2 7 4
输出#4
5 1
注意
在第一个示例中,所有道路都具有相同的美感。这意味着所有正长度的路径具有相同的中值。因此,任何长度从 3 到 4(含 3 和 4)的路径对我们来说都是有效的。
在第二个样本中,城市看起来像这样:1 - 2 - 3 - 4 - 5 - 6。最后两条路更有价值,我们应该选择包含这两条路且长度合适的任何路径。它要么是 2 到 6 之间的路径,要么是 3 到 6 之间的路径。