WWCITY - Thành phố WW
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: middlest

Thành phố WW có n khu đất được đánh số từ 1 đến n và m đường nối trực tiếp giữa hai khu đất. Biết rằng giữa hai khu đất bất kỳ luôn tồn tại đường đi từ khu đất này đến khu đất kia. Chính phủ muốn phong tỏa một khu đất để thực hiện dự án ACM. Khi một khu đất được chọn để thực hiện dự án, tất cả các đường nối trực tiếp giữa nó và các khu đất khác sẽ bị phá hủy. Để giảm thiệt hại cho người dân, Chính phủ sẽ chọn khu đất mà khi phá hủy đường để thực hiện dự án, số cặp khu đất còn lại không thể đi đến được nhau là bé nhất. Bạn đang làm trợ lý cho Chính phủ, hãy tính toán xem nên chọn khu đất nào để số cặp các khu đất còn lại không thể đi đến được nhau là bé nhất.

Dữ liệu vào

Dòng đầu gồm 2 số n, m

m dòng tiếp theo, mỗi dòng gồm 2 số u và v với ý nghĩa có đường nối trực tiếp giữa khu đất u và khu đất v

Dữ liệu ra

Gồm n dòng, dòng thứ i in ra số lượng các cặp khu đất không thể đi đến được nhau nếu như chọn khu đất thứ i để thực hiện dự án.

Giới hạn

1 <= n <= 105, 1 <= m <= 5x105

Ví dụ

  • input
    2 1
    1 2
    output
    2
    2

Nếu chọn thành phố 1 làm dự án, khi đó khu đất 1 không thể đến khu đất 2 và khu đất 2 không thể đến khu đất 1 nên kết quả là 2. Nếu chọn thành phố 2 ta có thể giải thích tương tự.

Back to Top