캠핑장의 자리 이동 기록

문제

한 캠핑장에는 일렬로 놓인 N개의 야영 구역이 있다. 구역에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있으며, 각 구역에는 텐트를 최대 하나만 설치할 수 있다. 관리실은 저녁 시간에 접수된 자리 이동 요청을 순서대로 처리하려고 한다. 이동하는 텐트의 주인이나 종류는 구분하지 않고, 각 구역에 텐트가 있는지만 기록한다. 처음 상태는 길이가 N인 문자열로 주어진다. 문자열의 i번째 문자가 1이면 i번 구역에 텐트가 하나 있고, 0이면 그 구역이 비어 있다. 이후 각 이동 요청에는 출발 구역 a와 도착 구역 b가 적혀 있다. 한 요청을 처리할 때에는 그 시점의 구역 상태를 확인한다. 출발 구역에 텐트가 있고 도착 구역이 비어 있으면 요청이 성공한다. 성공한 요청은 출발 구역의 텐트 하나를 도착 구역으로 옮긴다. 이에 따라 출발 구역은 비게 되고 도착 구역에는 텐트가 있게 된다. 출발 구역이 비어 있거나 도착 구역에 이미 텐트가 있으면 요청은 실패하며, 어느 구역의 상태도 바뀌지 않는다. 출발 구역과 도착 구역이 같은 요청도 접수될 수 있다. 이러한 요청은 항상 실패한 것으로 처리한다. 요청이 실패하더라도 뒤의 요청은 계속 처리한다. 앞선 요청의 성공이나 실패를 나중에 되돌리는 일은 없으며, 같은 두 구역을 지정한 요청도 각각 별개의 요청으로 처리한다. 관리실은 모든 요청을 처리한 뒤 성공한 요청의 총수와 최종 배치 상태를 보관하려고 한다. 요청이 하나도 없으면 성공 횟수는 0이고 최종 상태는 처음 상태와 같다. 처음부터 텐트가 하나도 없거나 모든 구역이 차 있는 상태도 주어질 수 있다. 요청을 입력된 순서대로 처리하여 관리실이 보관할 두 정보를 구한다.

입력

첫째 줄에 구역 수 N과 요청 수 M이 공백으로 구분되어 주어진다. N과 M은 정수이며 1 ≤ N ≤ 30,000, 0 ≤ M ≤ 30,000이다.
둘째 줄에 문자 0과 1로만 이루어진 길이 N의 문자열이 주어진다.
이후 M개의 줄에 정수 a와 b가 공백으로 구분되어 주어진다. 1 ≤ a, b ≤ N이다. a와 b가 같을 수도 있다.

출력

첫째 줄에 성공한 이동 요청의 총수를 정수로 출력한다. 둘째 줄에 최종 상태를 길이 N의 문자열로 출력한다. 각 구역이 비어 있으면 0, 텐트가 있으면 1을 구역 번호 순서대로 공백 없이 출력한다.

5 6
10100
1 2
3 2
3 5
1 4
2 2
5 1

3
11000

1 2
1
1 1
1 1

0
1

4 0
0000

0
0000

출처: Devin.KR 자체 제작