Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FSELECT - Làm quen bạn mới

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/fselect


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 ≤ 200000). 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.

Input

- Dòng 1 gồm 2 số NK.

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).

Output

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.

Example

Input:

6 2

1 3

2 1

1 0

2 1

2 1

1 5


Output:
3

2

Giải thích :

  -3-
|
-1-
/ | \
2 4 5
|
-6-


Trong cuộc hẹn thứ 1 gồm 3 bạn là bạn số 1, số 3 và số 6. Khoảng cách xa nhất giữa 2 ngôi nhà trong cuộc hẹn


thứ 1 là 3 ( giữa nhà bạn số 3 và số 6). Tương tự, cuộc hẹn thứ 2 gồm 3 bạn số 2, số 4 và số 5, khoảng cách 


xa nhất là 2.



Được gửi lên bởi:VOJ Team
Ngày:2011-10-24
Thời gian chạy:0.600s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP JAVA PAS-GPC PAS-FPC
Nguồn bài:USACO Holiday 2010 Bonus Competition

hide comments
2015-10-27 15:54:34 The Legendary Tiger (NDHD)
Tham khảo tại: https://copcode.wordpress.com/2015/10/27/fselect-spoj-lam-quen-ban-moi/
2015-10-05 15:23:57 bembembem
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). cho mình hỏi th thứ i là gốc à nếu y=0 ?
2015-08-11 17:55:27 N�ng D�n John
[đã hiểu đề] :v
2013-11-06 15:48:54 a;slkfjasl;fkj
đúng là đọc lúc đầu vẫn hơi khó hiểu :v
2011-11-06 06:58:22 Nguyễn Xuân Khánh
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).
2011-11-05 14:19:14 Hoang Van Tru
có ai có thể giúp mình hiểu rõ thêm đề bài được không ?. Mình vẫn chưa hiểu tại sao (ở trên ví dụ) ở cuộc hẹn thứ 1 lại là 3 bạn là bạn số 1, số 3 và số 6, và cuộc hẹn thứ 2 lại là 3 bạn số 2, số 4 và số 5. cám ơn nhiều, mình mới tham gia VOJ mong được sự giúp đỡ :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.