Trong một vương quốc xa xôi,có ~n+1~ thành phố được đánh số từ ~0~ đến ~n~ , kết nối với nhau bởi một mạng lưới gồm ~n~ con đường, mỗi thành phố không thể đi về lại chính thành phố mình nếu không đi về bằng các con đường đã đi.

Một ngày nọ, tổ chức Sariella, một tổ chức bí ẩn và đầy quyền lực, đã phát triển một loại Virus kỳ lạ với khả năng lây lan đặc biệt và nguy hiểm. Virus này có cơ chế lây nhiễm vô cùng phức tạp và khó lường, khiến cho việc kiểm soát và ngăn chặn trở nên vô cùng khó khăn.

Cơ chế lây nhiễm của Virus này được mô tả như sau:

Ở ngày thành phố ~i~

• Nếu một thành phố kề nó nhiễm bệnh vào ngày ~x-1~, thì vào ngày ~x~, Virus sẽ lây lan sang các thành phố ~i~ nếu ~i~ là lẻ.

• Nếu một thành phố bị nhiễm bệnh vào ngày ~x-2~,thì vào ngày ~x~, Virus sẽ tiếp tục lây lan sang các thành phố ~i~ nếu ~i~ là chẵn.

Quá trình này cứ tiếp diễn, tạo nên một chuỗi lây nhiễm liên tục và không ngừng nghỉ, như một cơn bão không thể kiểm soát.

Ban đầu, mỗi thành phố trong vương quốc sẽ bị nhiễm các loại Virus khác nhau,nhưng cơ chế lây lan lại giống nhau,mỗi Virus lây lan độc lập với nhau

Hỏi với mỗi thành phố, Virus bắt đầu ở thành phố ~i~ cần bao nhiêu ngày để lây nhiễu hết vương quốc.

Input

Dòng đầu là số nguyên ~n~ ~(2 \le n \le 10^6)~

~n~ dòng tiếp theo,mỗi dòng gồm 2 số nguyên ~u~ và ~v~,thể hiện thành phố ~u~ và ~v~ có ~1~ con đường đi qua nhau ~(0 \le u,v \le n)~

Output

Một dòng duy nhất có ~n+1~ số nguyên dương,số thứ ~i~ là thời gian cần để viruss bắt đầu từ thành phố ~i~ cố thể lây lan hết vương quốc

Sample Input

4
0 1
0 2
2 3
2 4

Sample Output

4 6 3 5 5

Giải thích

Ở thành phố ~i=0~:

• Thành phố ~1~ bị nhiễm ở ngày thứ nhất
• Thành phố ~2~ bị nhiễm ở ngày thứ hai
• Thành phố ~3~ bị nhiễm ở ngày thứ ba
• Thành phố ~4~ bị nhiễm ở ngày thứ tư

Ở thành phố ~i=1~:

• Thành phố ~0~ bị nhiễm ở ngày thứ ~2~
• Thành phố ~2~ bị nhiễm ở ngày thứ ~4~
• Thành phố ~3~ bị nhiễm ở ngày thứ ~5~
• Thành phố ~4~ bị nhiễm ở ngày thứ ~6~

Ở thành phố ~i=2~:

• Thành phố ~3~ bị nhiễm ở ngày thứ nhất
• Thành phố ~0~ và ~4~ bị nhiễm ở ngày thứ hai
• Thành phố ~1~ bị nhiễm ở ngày thứ ba

Ở thành phố ~i=3~:

• Thành phố ~2~ bị nhiễm ở ngày thứ ~2~
• Thành phố ~0~ và ~4~ bị nhiễm ở ngày thứ ~4~
• Thành phố ~1~ bị nhiễm ở ngày thứ ~1~

Ở thành phố ~i=4~:

• Thành phố ~2~ bị nhiễm ở ngày thứ ~2~
• Thành phố ~3~ bị nhiễm ở ngày thứ ~3~
• Thành phố ~0~ bị nhiễm ở ngày thứ ~4~
• Thành phố ~1~ bị nhiễm ở ngày thứ ~5~