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
2019-09-23 03:48:39
80 dòng
duonght_pro_xinhgainhathemattroi_:)
2019-09-07 16:35:25
stack limit codeblock chan vl
2019-09-04 17:25:15


Last edit: 2019-09-16 16:37:15
2017-12-28 13:08:29
2 đấm AC <3 (100 dòng)

Last edit: 2017-12-28 13:08:59
2017-11-15 11:03:08
nhật hào sạch
2017-10-04 09:46:21
Code AC: http://123link.top/FSELECT
2017-07-27 11:32:53
Code AC: http://shink.in/16CpJ
2017-07-26 04:14:28
đã 1 đấm AC = LCA+mô hình xếp hàng&cây IT :v 240 dòng :3


Last edit: 2017-07-27 05:20:01
2017-01-08 02:49:21
?
2016-02-01 09:21:29
THAM KHAO: http://codevnspoj.blogspot.com/
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.