문제
길이가 2N인 괄호 문자열이 주어진다.
또한, 1~2N 까지의 수가 각각 정확히 한 번씩 등장하는, 정수 두 개로 이루어진 순서쌍 (Ai, Bi)가 N개 주어진다.
여러분은 주어진 모든 순서쌍들에 대해, 정확히 한 쪽의 수를 활성화하려고 한다.
주어진 괄호 문자열에서 활성화된 번호의 괄호 문자만을 남겨놓았을 때, 남은 길이 N의 괄호 문자열을 활성화 문자열이라 정의하자.
활성화 문자열이 올바른 괄호 문자열이 되도록 순서쌍을 활성화할 수 있을지, 있다면 그 방법을 출력하시오.
빈 배열은 올바른 괄호 문자열이며,
올바른 괄호 문자열 두개를 붙인 괄호문자열 또한 올바른 괄호 문자열이고,
올바른 괄호 문자열 왼쪽에 '('를, 오른쪽에 ')'를 추가한 괄호 문자열 또한 올바른 괄호 문자열이다.
입력
첫 줄에 테스트 케이스의 개수 T(1<=T<=100000)가 주어진다.
각 테스트 케이스 별로, 첫 줄에 N(1<=N<=100000)이 주어진다.
이때 모든 테스트 케이스에 대한 N의 합은 항상 100000 이하이다.
둘째 줄에는 길이 2N인 괄호 문자열이 주어진다.
이후 N개의 줄에 걸쳐 1~2N 까지의 수가 정확히 한 번씩 등장하는 순서쌍 Ai, Bi가 총 N개 주어진다.
Subtask 1 (9점) : 1<=N<=10
Subtask 2 (17점) : 모든 i에 대해, Ai번 괄호와 Bi번 괄호의 종류가 같다.
Subtask 3 (29점) : 모든 i에 대해, Ai+1=Bi 이다.
Subtask 4 (45점) : 제한 없음
출력
각 테스트 케이스 별로 정답을 한 줄씩 출력한다.
만약 올바른 괄호 문자열인 활성화 문자열이 존재하지 않는다면, -1을 출력한다.
존재한다면, i번째 순서쌍부터 Ai가 활성화된다면 0, Bi가 활성화된다면 1을 공백으로 구분하여 출력한다.
예제1
1
4
()))((()
12
35
46
78
0101
예제2
2
4
)()()()(
12
34
56
78
3
(()())
16
24
35
1100
-1