Đóng cửa thành phố

Có $n$ thành phố đánh số từ $1$ đến $n$ và $m$ con đường hai chiều, con đường thứ $i$ nối hai thành phố $u_i$ và $v_i$. Có thể có nhiều con đường nối cùng một cặp thành phố.

Với mỗi thành phố $x$, giả sử thành phố $x$ bị đóng cửa: nó và mọi con đường nối tới nó bị bỏ đi. Hãy cho biết $n-1$ thành phố còn lại chia thành bao nhiêu vùng, biết rằng hai thành phố cùng một vùng khi và chỉ khi đi được từ thành phố này tới thành phố kia bằng các con đường còn lại.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i,v_i$.

Dữ liệu ra

In ra $n$ dòng, dòng thứ $x$ là số vùng khi thành phố $x$ bị đóng cửa.

Ràng buộc

• $1\le n\le {10}^5$
• $0\le m\le 1.5·{10}^5$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$

Ví dụ