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

Sửa cạnh

Đị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

Mạng lưới giao thông của thành phố FPTOJ gồm \(N\) nút giao thông được nối với nhau bởi \(N-1\) tuyến đường. Mỗi tuyến đường có một thời gian di chuyển nhất định (là số nguyên dương). Do tình hình đô thị hóa, thời gian di chuyển trên các tuyến đường có thể thay đổi theo từng ngày (do sửa chữa hoặc nâng cấp). Sở giao thông muốn xây dựng một hệ thống theo dõi, có thể thực hiện hai loại yêu cầu: (1) Cập nhật thời gian của một tuyến đường nào đó. (2) Trả lời truy vấn: đi từ nút \(u\) đến nút \(v\), thời gian ngắn nhất (nhỏ nhất) và dài nhất (lớn nhất) trên tuyến đường đó là bao nhiêu.

Yêu cầu: Cho \(N\) nút giao thông và \(N-1\) tuyến đường. Xử lý \(Q\) yêu cầu thuộc một trong hai loại:

• Loại \(1\) \(u\) \(v\) \(w\): cập nhật tuyến đường giữa \(u\) và \(v\) thành thời gian \(w\).
• Loại \(2\) \(u\) \(v\): in ra thời gian nhỏ nhất và lớn nhất 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 bắt đầu bằng số \(1\) hoặc \(2\):
  • \(1\) \(u\) \(v\) \(w\): cập nhật.
  • \(2\) \(u\) \(v\): truy vấn.

Kết quả:

• Với mỗi yêu cầu loại \(2\), in ra hai số: thời gian nhỏ nhất và lớn nhất trên đường đi.

Ví dụ:

Dữ liệu vào:

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

Kết quả:

2 5
2 10
7 10

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 |