시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 111 29 29 63.043%

문제

0과 1로만 이루어져 있으며, 0의 개수와 1의 개수가 동일한 문자열 S가 주어진다. 당신은 S에 다음과 같은 작업을 여러 번 수행할 수 있다:

S의 길이 2k인 연속한 부분문자열이 앞 k개 문자가 모두 동일하고, 또한 뒤 k개 문자가 서로 동일하며, 0과 1을 모두 포함할 때, 그 부분문자열을 제거할 수 있다.

예를 들어, S = “0111000011”인 경우, S의 2번째 문자부터 7번째 문자까지인 “111000”을 제거하는 것이 가능하다. 이 작업 후에는 제거된 부분의 앞부분과 뒷부분이 연결되어 S = “0011”이 된다. 그러면 이제 한 번의 작업을 통해 “0011”을 제거할 수 있으므로 초기 S = “0111000011”는 두 번의 작업을 통해 빈 문자열로 만들 수 있다.

여러분의 목표는 최소 횟수의 작업을 통해 S를 빈 문자열로 만드는 것이다. 최소 횟수의 작업으로 S를 빈 문자열로 만드는 과정을 구하여라.

입력

첫 줄에 0과 1로만 이루어진 문자열 S가 주어진다. S에 포함된 0의 개수와 1의 개수는 동일하다.

출력

작업들을 통해 S를 빈 문자열로 만드는 것이 불가능하다면 첫 줄에 -1을 출력한다.

그렇지 않은 경우, 첫 줄에 필요한 작업의 최소 횟수 K를 출력한다. 그 다음 K줄에 걸쳐 수행한 작업에 대한 정보를 출력한다.

K개 줄 중 i번째 줄에는 두 정수 biei를 공백을 사이에 두고 출력한다. 이는 i번째 작업에서 Sbi번째 문자부터 ei번째 문자로 이루어진 문자열을 제거하였음을 뜻한다.

최소 횟수의 작업으로 문자열을 지우는 방법이 여러 가지인 경우에는 그 중 아무 것이나 출력해도 된다.

제한

  • S에 포함된 문자의 개수는 1 이상 500,000 이하이다.
  • S에 포함된 0의 개수와 1의 개수는 동일하다.

예제 입력 1

0101110100

예제 출력 1

4
2 3
4 5
3 6
1 2

처음에 S = "0101110100''인 상태이다.

Si번째 문자부터 j번째 문자까지의 문자열을 S[i:j]라 하자.

S[2:3] = "10''을 제거하면 S = "01110100''이 된다.

그 후 S[4:5] = "10''을 제거하면 S = "011100''이 되고,

다음에 S[3:6] = "1100''을 제거하면 S = "01''이 된다.

마지막으로 S[1:2] = "01''을 제거하면 S는 빈 문자열이 된다.

S = "0101110100''을 4번 미만의 작업을 통해 빈 문자열로 만드는 방법은 존재하지 않는다.