Tàu điện ngầm

Điểm: 5,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

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 \leq n \leq 3000$ ).
$n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_{i}, y_{i}$ ( $1 \leq x_{i}, y_{i} \leq n$ , $x_{i} \neq 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 \leq n \leq 3000$
Đồ thị liên thông, có đúng $n$ cạnh, không có cạnh bội.

Ví dụ

Input	Output	Giải thích
4 1 3 4 3 4 2 1 2	0 0 0 0	Toàn bộ 4 trạm tạo thành đường vành đai $1 - 2 - 4 - 3 - 1$ .
6 1 2 3 4 6 4 2 3 1 3 3 5	0 0 0 1 1 2	Đường vành đai là $1 - 2 - 3 - 1$ . Trạm $4$ và $5$ cách đai $1$ ray, trạm $6$ cách đai $2$ ray (qua trạm $4$ ).

Bình luận

Không có bình luận tại thời điểm này.