// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
template<class T> using V = vector<T>;
using vi = V<int>;
void solve() {
int N; cin >> N;
string S; cin >> S;
V<array<int, 2>> A(N); for(auto& x : A) { cin >> x[0] >> x[1]; --x[0], --x[1]; }
if (N % 2) {
cout << -1 << nl;
return;
}
vi I(2 * N, -1); int open = N / 2; vi ans(N, -1), take(2 * N, 0);
for(int i = 0; i < N; i++) {
int x = A[i][0], y = A[i][1];
if (S[x] == S[y]) {
if (S[x] == '(') { ans[i] = 0; open--; take[x] = 1; } // take first
else { ans[i] = 1; take[y] = 1; } // take last
} else {
I[x] = 2 * i;
I[y] = 2 * i + 1;
}
}
for(int i = 0; i < 2 * N; i++) if (I[i] != -1) {
int x = I[i] / 2, j = A[x][1];
if (S[i] == '(') {
if (open > 0) { open--; ans[x] = 0; take[i] = 1; }
else { ans[x] = 1; take[j] = 1; }
} else {
if (open > 0) { open--; ans[x] = 1; take[j] = 1; }
else { ans[x] = 0; take[i] = 1; }
}
I[i] = I[j] = -1;
}
int bal = 0; for(int i = 0; i < 2 * N; i++) if (take[i]) {
if (S[i] == '(') bal++;
else bal--;
if (bal < 0) {
cout << -1 << nl;
return;
}
}
if (bal != 0) {
cout << -1 << nl;
return;
}
for(auto& x : ans) cout << x << " ";
cout << nl;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int T; cin >> T; while(T--) {
solve();
}
exit(0-0);
}
