Page not loading? Try clicking here.
Placeholder

#8262

접근가능쌍 1s 1024MB

Problems

무방향 그래프가 N (1 \leq N \leq 2 \cdot 10^5) 개의 노드와 M (0 \leq M \leq 4 \cdot 10^5) 개의 간선을 가진다. 노드는 1부터 N까지 번호가 매겨져 있다. 길이 N 인 이진 문자열 s_1s_2 \dots s_N​ 가 주어진다.

각 시간 t (t \in [1, N]) 에 대해 다음 작업을 수행한다.

  • 만약 s_t = 0 이면, 노드 t 를 그래프에서 제거한다.

  • 만약 s_t = 1 이면, 노드 t 를 그래프에서 제거하고, 제거되기 직전의 이웃들 사이에 간선을 추가한다.

각 시간 t 직전에 서로 도달 가능한 노드 쌍의 개수를 출력한다.


Input

첫 번째 줄에 N 과 M 이 주어진다.

두 번째 줄에 길이 N 의 이진 문자열 s 가 주어진다.

다음 M 개의 줄에 각 간선을 나타내는 두 정수 u, v 가 주어진다.


Output

N 개의 줄을 출력하며, 각 줄에 타임스텝 t 직전까지 서로 도달 가능한 노드 쌍의 개수를 출력한다.


Subtask

# Score Condition
#120

N≤100

#215

모든 s_i는 0이다.

#315

모든 s_i는 1이다.

#450

추가 제약 조건 없음


Example #1

3 2
111
1 2
1 3
3
1
0

노드가 제거되기 전에는 모든 노드 쌍이 서로 도달 가능하다. 노드 1이 제거된 후, 2와 3 사이에 간선이 추가되므로 여전히 서로 도달할 수 있다.


Example #2

3 2
000
1 2
1 3
3
0
0

노드가 제거되기 전에는 모든 노드 쌍이 서로 도달 가능하다. 노드 1이 제거된 후, 2와 3은 더 이상 서로 도달할 수 없다.


Example #3

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


Source

USACO 2025 January Gold

You must sign in to write code.