\(1\)번부터 \(N\)번까지 번호가 붙은 \(N\)개의 노드와 \(M\)개의 간선으로 이루어진 무방향 그래프를 생각하자. \((1 \le N \le 200,000,\ 0 \le M \le 400,000)\) 이진 문자열 \(s_1s_2\ldots s_N\)이 주어진다.

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

• \(s_t=0\)이면 그래프에서 노드 \(t\)를 제거한다.
• \(s_t=1\)이면 그래프에서 노드 \(t\)를 제거하고, 노드 \(t\)를 제거하기 직전에 이웃이었던 모든 노드 쌍 사이에 간선을 추가한다.

두 경우 모두 그래프에서 노드가 제거되면 그 노드와 연결된 모든 간선도 함께 제거된다.

\(1\)부터 \(N\)까지의 각 시간 단계가 시작되기 직전에, 간선들을 따라 서로 도달할 수 있는 노드 쌍의 수를 구하여라.

입력

첫째 줄에 \(N\)과 \(M\)이 주어진다.

둘째 줄에 길이가 \(N\)인 이진 문자열 \(s\)가 주어진다.

다음 \(M\)개의 줄에는 그래프의 간선 하나를 나타내는 두 정수가 주어진다.

출력

\(N\)개의 줄을 출력한다. 각 줄에는 해당 시간 단계가 시작되기 직전에 서로 도달할 수 있는 노드 쌍의 수를 출력한다.

예제 입력 1

3 2
111
1 2
1 3

예제 출력 1

3
1
0

예제 설명 1

어떤 노드도 제거되기 전에는 모든 노드 쌍이 서로 도달할 수 있다. \(1\)번 노드가 제거된 뒤에는 \(2\)번 노드와 \(3\)번 노드 사이에 간선이 추가되므로, 두 노드는 여전히 서로 도달할 수 있다.

예제 입력 2

3 2
000
1 2
1 3

예제 출력 2

3
0
0

예제 설명 2

어떤 노드도 제거되기 전에는 모든 노드 쌍이 서로 도달할 수 있다. \(1\)번 노드가 제거된 뒤에는 \(2\)번 노드와 \(3\)번 노드가 더 이상 서로 도달할 수 없다.

예제 입력 3

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

예제 출력 3

11
7
4
2
1
1
0

출처

USACO 2025 January Contest, Gold, Problem 2. Reachable Pairs