Xét một đồ thị vô hướng gồm \(N\) đỉnh được đánh số \(1\dots N\) và \(M\) cạnh (\(1\le N\le 2\cdot 10^5, 0\le M\le 4\cdot 10^5\)). Bạn được cho một chuỗi nhị phân \(s_1s_2\dots s_N\). Tại thời điểm \(t\) với mỗi \(t\in [1,N]\):

• Nếu \(s_t=0\), đỉnh \(t\) bị xóa khỏi đồ thị.
• Nếu \(s_t=1\), đỉnh \(t\) bị xóa khỏi đồ thị, đồng thời các cạnh được thêm vào giữa mọi cặp đỉnh kề với đỉnh \(t\) ngay trước khi nó bị xóa.

Lưu ý rằng trong cả hai trường hợp, khi một đỉnh bị xóa khỏi đồ thị, tất cả các cạnh liên thuộc với nó cũng bị xóa.

Hãy đếm số cặp đỉnh có thể đi tới nhau qua một dãy cạnh nào đó ngay trước mỗi thời điểm \(1\ldots N\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\).

Dòng thứ hai chứa chuỗi bit \(s\) có độ dài \(N\).

\(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên biểu diễn một cạnh của đồ thị.

Dữ liệu ra

In \(N\) dòng, là số cặp trước mỗi thời điểm.

Ví dụ

3 2
111
1 2
1 3

3
1
0

3 2
000
1 2
1 3

3
0
0

7 8
1101101
6 2
1 2
2 3
6 3
1 3
1 7
4 5
2 7

11
7
4
2
1
1
0

Phân nhóm

• Inputs 4-6: \(N\le 100\).
• Inputs 7-8: Mọi \(s_i\) đều bằng không.
• Inputs 9-11: Mọi \(s_i\) đều bằng một.
• Inputs 12-23: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Gold — Reachable Pairs

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1474

Tác giả đề: Benjamin Qi