Kiểm Tra Bò

Cho đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh, cùng xâu nhị phân $s$ có độ dài $N$. Tại mỗi bước thời gian $t$ (từ $1$ đến $N$):

• Nếu $s_t=0$: đỉnh $t$ bị xóa (cùng tất cả cạnh liên quan)
• Nếu $s_t=1$: đỉnh $t$ bị xóa, nhưng trước khi xóa, thêm cạnh giữa mọi cặp hàng xóm của $t$

Hãy đếm số cặp đỉnh có thể đến được nhau (qua dãy cạnh) ngay trước mỗi bước thời gian $1,2,\dots ,N$.

Dữ liệu vào

• Dòng 1: Hai số $N$ và $M$
• Dòng 2: Xâu nhị phân $s$ có độ dài $N$
• $M$ dòng tiếp: Mỗi dòng hai số mô tả một cạnh

Dữ liệu ra

• $N$ dòng, dòng thứ $t$ chứa số cặp đỉnh liên thông ngay trước bước $t$.

Ràng buộc

• $1\le N\le 2·{10}^5$
• $0\le M\le 4·{10}^5$

Ví dụ