Tý cần giải bài toán sau:

Lubenica gốc

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Tại làng Lubenica nhỏ bé, có \(N\) khu vườn được nối với nhau bởi \(N-1\) con đường lát đá. Mỗi con đường có một độ dốc nhất định (là số nguyên dương). Các bác nông dân thường xuyên di chuyển giữa các khu vườn để trao đổi nông sản. Bác trưởng làng muốn biết, đối với mỗi tuyến đường từ vườn \(u\) đến vườn \(v\), con đường dốc nhất và con đường thoải nhất lần lượt có độ dốc là bao nhiêu, để có thể phân công các xe bò phù hợp.

Yêu cầu: Cho \(N\) khu vườn và \(N-1\) con đường. Trả lời \(Q\) truy vấn, mỗi truy vấn yêu cầu in ra giá trị nhỏ nhất và lớn nhất của các cạnh trên đường đi từ \(u\) đến \(v\).

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương \(N\).
• \(N-1\) dòng tiếp theo, mỗi dòng gồm ba số \(u\), \(v\), \(w\).
• Dòng tiếp theo chứa số nguyên dương \(Q\).
• \(Q\) dòng sau, mỗi dòng gồm hai số \(u\), \(v\).

Kết quả:

• In ra \(Q\) dòng, mỗi dòng gồm hai số: giá trị nhỏ nhất và lớn nhất của các cạnh trên đường đi.

Ví dụ:

Dữ liệu vào:

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

Kết quả:

2 5
2 7
2 3

Giới hạn: | Subtask | \(N\) | \(Q\) | Điểm | |---------|-----|-----|------| | 1 | ≤ 100 | ≤ 100 | 5 | | 2 | ≤ 500 | ≤ 500 | 5 | | 3 | ≤ 2 000 | ≤ 2 000 | 10 | | 4 | ≤ 10 000 | ≤ 10 000 | 10 | | 5 | ≤ 50 000 | ≤ 50 000 | 15 | | 6 | ≤ 100 000 | ≤ 100 000 | 15 | | 7 | ≤ 100 000 | ≤ 100 000 | 20 | | 8 | ≤ 100 000 | ≤ 100 000 | 20 |