Sau khi tham dự IOI và OLPSV, Nguyên chuyển đến một ngôi nhà mới. Khu nhà mới của Nguyên có N người bạn hàng xóm (N ≤ 200.000). Vì dễ bị nhầm nên Nguyên đánh số các bạn ấy từ 1 đến N. Giữa các ngôi nhà có đường đi tạo thành cây. Khoảng cách giữa hai căn nhà kề nhau là 1 đơn vị. Có K cuộc hẹn ( K ≤ N/2) được Nguyên đưa ra để làm quen với các bạn mới. Để tính toán chi phí mời các bạn, Nguyên muốn biết xem khoảng cách xa nhất của 2 ngôi nhà trong một cuộc hẹn là bao nhiêu ? Bạn hãy giúp Nguyên giải quyết vấn đề này.
Dữ liệu vào:
- Dòng 1 gồm 2 số N và K.
- N dòng tiếp theo, dòng thứ i gồm 2 số x y. Trong đó x là thứ tự của cuộc hẹn mà bạn thứ i tham gia, y là nhà hàng xóm của bạn thứ i. Nếu y = 0 thì đó là gốc của khu dân cư (có thể hiểu là gốc của cây).
Dữ liệu ra:
- Gồm K dòng, dòng thứ i thể hiện đường đi xa nhất tìm được giữa 2 ngôi nhà của 2 người bạn trong cuộc hẹn thứ i.