ABC Legacy

시간 제한1초메모리 제한1024 MB

요약

길이 2n인 문자열을 AB, AC, BC 중 하나를 이루는 n개의 서로 겹치지 않는 증가하는 인덱스 쌍으로 나눌 수 있는지 판정하고 구성한다.

난이도: 보통10점 중 7점
유형: 그리디, 스택
정답자: 아직 제출이 없습니다

문제

You are given a string $S$ of length $2n$ , consisting of the characters A, B and C. Determine if $S$ can be split into $n$ non-intersecting subsequences, each of which forms one of the strings "AB", "AC", "BC". If it is possible, find such a splitting.

입력

The first line of input contains one integer $n$ ( $1 \le n \le 10^5$ ).

The second line of input contains a string $S$ of length $2n$ , consisting of the characters A, B and C.

출력

If the splitting is not possible, print "NO" (without quotes).

If the splitting is possible, print "YES" (without quotes), followed by $n$ lines, each describing two indices for the $i$ -th subsequence ( $1 \le l\_i < r\_i \le 2n$ ).

예제4

예제 1
입력
```
3
BABBCC
```
예상 출력
```
YES
3 5
1 6
2 4
```
예제 2
입력
```
2
CBAC
```
예상 출력
```
NO
```
예제 3
입력
```
1
AA
```
예상 출력
```
NO
```
예제 4
입력
```
3
ABCACB
```
예상 출력
```
YES
2 3
4 6
1 5
```