\text{Đường đi dài nhất}

Đị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èo đang khám phá khu rừng FPTOJ với \(N\) cây và \(N-1\) con đường. Mỗi con đường có độ dài \(w_i\). Tèo muốn tìm hai cây xa nhau nhất trong khu rừng, tức là đường đi giữa chúng có tổng độ dài lớn nhất.

Yêu cầu: Tìm đường kính (diameter) của cây - đường đi dài nhất giữa hai đỉnh bất kỳ.

Đầu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa \(u, v, w\) với \(w\) là độ dài (\(1 \le w \le 10^6\)).

Đầu ra

• In ra độ dài đường đi dài nhất.

Ví dụ

Đầu vào:

4
1 2 5
2 3 10
2 4 7

Đầu ra:

17

Giải thích

Đường đi từ 3 đến 4: \(3 \to 2 \to 4\) có độ dài \(10 + 7 = 17\).

Subtask