괄호 문자열 이동하기

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

요약

길이가 같은 두 올바른 괄호 문자열 S와 T가 주어질 때, 안쪽 부분 문자열이 항상 올바른 괄호 문자열이 되도록 하는 교환만 사용해 S를 T로 바꾸는 과정을 출력한다.

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

문제

올바른 괄호 문자열(VPS)은 다음과 같이 정의한다.

빈 문자열은 VPS이다.
S가 VPS라면 (S)도 VPS이다.
S와 T가 VPS라면 ST도 VPS이다.
모든 VPS는 위 세 가지 규칙으로만 만들 수 있다.

예를 들어 "(())()", "()()()", "(()())” 등은 VPS이고, "())(()", "(", "(()()()" 등은 VPS가 아니다.

VPS를 좋아하는 태수는 길이가 $N$ 인 VPS $S$ 를 선물 받았다. 하지만 태수의 위시리스트에 담겨있던 VPS는 $T$ 였기에, $S$ 의 두 문자를 바꾸는 작업을 최대 $N$ 번 해서 $T$ 로 만들고 싶었다. 하지만 VPS를 좋아하는 태수는 다음과 같은 조건들을 만족할 때만 두 원소를 바꾸기로 했다.

$1 \leq L < R \leq N$ 을 만족하는 $L$ , $R$ 에 대해 $S\[L]$ 과 $S\[R]$ 을 바꾼다고 할 때, 두 문자 사이에 있는 문자열도 VPS여야한다. 즉, $R-L=1$ 을 만족하거나 $S\[L+1 ... R-1]$ 이 VPS여야한다. 또한, 두 문자를 바꾼 뒤에도 $S$ 는 VPS여야 한다.

태수를 위해 $S$ 를 $T$ 로 바꾸는 방법을 알려주자. 답이 반드시 존재함을 증명할 수 있다.

입력

첫째 줄에 테스트케이스의 개수 $C$ 가 주어진다. $(1 \leq C \leq 5 \times 10^5)$

각 테스트케이스 별로 입력은 다음과 같이 주어진다.

첫째 줄에 정수 $N$ 이 주어진다. $(1 \leq N \leq 10^6)$

둘째 줄에 길이가 $N$ 인 VPS $S$ 가 주어진다.

셋째 줄에 길이가 $N$ 인 VPS $T$ 가 주어진다.

모든 테스트케이스의 $N$ 의 합은 $10^6$ 을 넘지 않는다.

출력

각 테스트케이스 별로 다음과 같이 출력한다.

첫째 줄에 작업 횟수 $X$ $(0 \leq X \leq N)$ 를 출력한다.

둘째 줄부터 $X$ 줄에 걸쳐, 바꾸는 두 원소의 인덱스 $L$ $R$ 을 작업 순서에 맞춰 출력한다.

반드시 작업 횟수가 최소가 될 필요는 없다.

예제1

예제 1

입력

2
6
(())()
()(())
4
()()
(())

예상 출력