Mô tả

Cho một cây gồm ~N~ đỉnh (đánh số từ ~1~ đến ~N~). Mỗi cạnh ~(a,b)~ có độ dài (trọng số) là một số nguyên dương ~c~.

Với một đường đi đơn giản (không lặp đỉnh) gồm ~k~ cạnh, độ dài Chef của đường đi được định nghĩa là trung vị trên của các độ dài cạnh nằm trên đường đi đó:

• Lấy tất cả độ dài các cạnh của đường đi, bỏ vào một mảng.
• Sắp xếp mảng theo thứ tự không giảm.
• Nếu ~k~ lẻ, trung vị là phần tử ở chính giữa.
• Nếu ~k~ chẵn, trung vị là phần tử lớn hơn trong hai phần tử ở giữa (tức phần tử thứ ~\lfloor k/2 \rfloor + 1~ nếu đánh số từ 1).

Ví dụ:

• ~\{3,7,9\}~ → trung vị = ~7~.
• ~\{1,2,3,4\}~ → hai phần tử giữa là ~2,3~, trung vị (trên) = ~3~.

Bạn được cho hai số ~L~ và ~R~ (số cạnh). Hãy tìm giá trị nhỏ nhất của ~độ dài Chef~ trong tất cả các đường đi đơn giản có ít nhất ~L~ cạnh và nhiều nhất ~R~ cạnh. Nếu không có đường đi nào có số cạnh nằm trong ~[L, R]~, hãy in -1.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~T~ — số bộ test.

• Với mỗi bộ test:

  • Dòng đầu chứa ba số nguyên ~N, L, R~.
  • Mỗi dòng trong ~N-1~ dòng tiếp theo chứa ba số nguyên ~a, b, c~ — cạnh nối đỉnh ~a~ và ~b~ có độ dài ~c~.

Dữ liệu ra

Với mỗi bộ test, in trên một dòng giá trị độ dài Chef nhỏ nhất trong số các đường đi thỏa điều kiện ~L \le k \le R~; nếu không tồn tại đường đi như vậy, in -1.

Ràng buộc

• ~1 \le T \le 5 \times 10^{4}~
• ~2 \le N \le 10^{5}~
• ~2 \le L \le R \le 50~
• ~1 \le a, b \le N~
• ~1 \le c \le 10^{9}~
• Tổng ~N~ của tất cả bộ test trong một file không vượt quá ~3 \times 10^{5}~
• Dữ liệu luôn tạo thành một cây

Nhiệm vụ phụ

• Subtask 1 (27 điểm):

  • Tổng ~N~ trên tất cả các test ~\le 1000~
  • Giới hạn thời gian 1 giây

• Subtask 2 (73 điểm):

  • Ràng buộc gốc như trên
  • Giới hạn thời gian 6 giây

Ví dụ

Input

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

Output

1
2

Giải thích

Test #1

Liệt kê các đường đi hợp lệ (số cạnh 2 hoặc 3) và trung vị:

• 1–3–6, độ dài = {3, 2} → Chef = 3
• 1–2–4, độ dài = {1, 1} → Chef = 1
• 1–2–5, độ dài = {1, 2} → Chef = 2
• 2–1–3, độ dài = {1, 3} → Chef = 3
• 2–1–3–6, độ dài = {1, 3, 2} → Chef = 2
• 4–2–5, độ dài = {1, 2} → Chef = 2
• 4–2–1–3, độ dài = {1, 1, 3} → Chef = 1
• 5–2–1–3, độ dài = {2, 1, 3} → Chef = 2 (và các đường đi ngược chiều tương ứng).

Giá trị nhỏ nhất thu được là 1 ⇒ đáp án là 1.

Test #2

Các đường đi hợp lệ:

• 1–2–3–4, độ dài = {1, 3, 4} → Chef = 3
• 2–3–4–5, độ dài = {1, 2, 4} → Chef = 2
• 1–2–3–4–5, độ dài = {1, 2, 3, 4} → Chef = 3

Giá trị nhỏ nhất là 2 ⇒ đáp án 2.

Ghi chú

Một đường đi đơn giản là đường đi không lặp lại đỉnh.