Mô tả và yêu cầu

Liên thông

Cho một đồ thị vô hướng gồm 𝑛 đỉnh đánh số từ 1 tới 𝑛 và 𝑚 cạnh đánh số từ 1
tới 𝑚.
Cạnh thứ 𝑖 nối giữa hai đỉnh 𝑢𝑖, 𝑣𝑖. Nếu ta xoá đi một đỉnh nào đó của đồ thị, số
thành phần liên thông của đồ thị có thể tăng lên. Nhiệm vụ của bạn là với mỗi
đỉnh, hãy tính xem nếu ta xoá đỉnh đó đi thì đồ thị mới nhận được có bao nhiêu
thành phần liên thông.

Dữ liệu: Vào từ file văn bản GRAPH2.INP

• Dòng đầu chứa hai số nguyên dương 𝑛, 𝑚 (𝑛 ≤ 20000; 𝑚 ≤ 50000)

• 𝑚 dòng sau, dòng thứ 𝑖 chứa hai số nguyên dương 𝑢𝑖, 𝑣𝑖.

Kết quả: Ghi ra file văn bản GRAPH2.OUT

• 𝑛 dòng, dòng thứ 𝑗 cho biết số thành phần liên thông của đồ thị nếu ta xóa
đi đỉnh
𝑗.

Ví dụ

GRAPH2.INP  GRAPH2.OUT
                                     4 3                 1
                                     1 2                 3
                                     2 3                 1
                                     2 4                 1


Chú ý: Ít nhất 60% số điểm ứng với các test có           𝑛 ≤ 1000; 𝑚 ≤ 2000