Tàu điện ngầm

Một hệ thống tàu điện ngầm được mô tả bởi $n$ trạm và $n$ đường ray (cạnh vô hướng), mỗi đường ray nối đúng hai trạm khác nhau. Giữa hai trạm bất kỳ có nhiều nhất một đường ray, và từ một trạm bất kỳ ta có thể đi tới mọi trạm còn lại bằng cách di chuyển dọc theo các đường ray.

Một đồ thị liên thông gồm $n$ đỉnh và $n$ cạnh luôn chứa đúng một chu trình đơn — gọi là đường vành đai. Với mỗi trạm $i$, hãy tính khoảng cách (số đường ray) ngắn nhất từ trạm đó tới một trạm bất kỳ nằm trên đường vành đai. Các trạm thuộc đường vành đai có khoảng cách bằng $0$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ ($3\le n\le 3000$).
• $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i,y_i$ ($1\le x_i,y_i\le n$, $x_i\ne y_i$) mô tả một đường ray nối hai trạm $x_i$ và $y_i$.

Dữ liệu đảm bảo đồ thị liên thông, có đúng $n$ cạnh và không có cạnh trùng nhau.

Dữ liệu ra

In ra $n$ số nguyên trên một dòng, cách nhau bởi dấu cách. Số thứ $i$ là khoảng cách từ trạm $i$ tới đường vành đai.

Ràng buộc

• $3\le n\le 3000$
• Đồ thị liên thông, có đúng $n$ cạnh, không có cạnh bội.

Ví dụ