Lubenica gốc

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 | \(N \le 100\) | \(Q \le 100\) | 5 | | 2 | \(N \le 500\) | \(Q \le 500\) | 5 | | 3 | \(N \le 2000\) | \(Q \le 2000\) | 10 | | 4 | \(N \le 10000\) | \(Q \le 10000\) | 10 | | 5 | \(N \le 50000\) | \(Q \le 50000\) | 15 | | 6 | \(N \le 100000\) | \(Q \le 100000\) | 15 | | 7 | \(N \le 100000\) | \(Q \le 100000\) | 20 | | 8 | \(N \le 100000\) | \(Q \le 100000\) | 20 |

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

• Dòng 1: Số nguyên \(N\) (\(1 \le N \le 10^5\)). - N-\(1\) dòng tiếp theo: mỗi dòng chứa 3 số nguyên \(u, v, w\) (\(1 \le u, v \le N, 1 \le w \le 10^9\)).
• Dòng tiếp theo: Số nguyên \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dòng tiếp theo: mỗi dòng chứa 2 số nguyên \(u, v\).

Định dạng đầu ra

• Với mỗi truy vấn, in ra 2 số nguyên là giá trị nhỏ nhất và lớn nhất của trọng số các cạnh trên đường đi \(u \to v\).

Ví dụ

Input:

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

Output:

5 8
3 8

Giải thích: Đường đi 1->3 có min=5, max=8. Đường đi 3->4 có min=3, max=8.

Ràng buộc & Subtasks