#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (auto x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
struct node{
int s,e,m;
int val=0,lazy=0;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void propo(){
if (lazy){
val+=lazy;
if (s!=e){
l->lazy+=lazy;
r->lazy+=lazy;
}
lazy=0;
}
}
void update(int i,int j,int k){
if (s==i && e==j) lazy+=k;
else{
if (j<=m) l->update(i,j,k);
else if (m<i) r->update(i,j,k);
else l->update(i,m,k),r->update(m+1,j,k);
l->propo(),r->propo();
val=min(l->val,r->val);
}
}
int query(int i,int j){
propo();
if (s==i && e==j) return val;
else if (j<=m) return l->query(i,j);
else if (m<i) return r->query(i,j);
else return min(l->query(i,m),r->query(m+1,j));
}
int find(){
propo();
if (s==e) return s;
l->propo(),r->propo();
if (l->val<0) return l->find();
else return r->find();
}
} *root;
struct node2{
int s,e,m;
ii val;
node2 *l,*r;
node2 (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
val=ii(1e9,-1);
if (s!=e){
l=new node2(s,m);
r=new node2(m+1,e);
}
}
void update(int i,ii k){
if (s==e) val=k;
else{
if (i<=m) l->update(i,k);
else r->update(i,k);
val=min(l->val,r->val);
}
}
ii query(int i,int j){
if (s==i && e==j) return val;
else if (j<=m) return l->query(i,j);
else if (m<i) return r->query(i,j);
else return min(l->query(i,m),r->query(m+1,j));
}
} *root2;
int n;
string s;
ii arr[100005];
int ans[100005];
signed main(){
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
int TC;
cin>>TC;
while (TC--){
cin>>n;
cin>>s;
rep(x,0,n){
cin>>arr[x].fi>>arr[x].se;
arr[x].fi--,arr[x].se--;
}
if (n%2==1){
cout<<"-1"<<endl;
continue;
}
root=new node(0,2*n);
root2=new node2(0,2*n);
int num=0;
rep(x,0,n){
if (s[arr[x].fi]==s[arr[x].se]){
if (s[arr[x].fi]=='('){
ans[x]=0;
root->update(arr[x].fi,2*n,1);
}
else{
ans[x]=1;
root->update(arr[x].se,2*n,-1);
}
}
else{
if (s[arr[x].fi]==')'){
ans[x]=0;
root->update(arr[x].fi,2*n,-1);
}
else{
ans[x]=1;
root->update(arr[x].se,2*n,-1);
}
num++;
root2->update(arr[x].fi,{arr[x].se,x});
}
}
int tot=root->query(2*n,2*n);
if (tot>0 || tot<-2*num){
cout<<"-1"<<endl;
continue;
}
bool bad=false;
while (root->query(2*n,2*n)){
int pos=root->find();
ii temp=root2->query(0,2*n);
//cout<<temp.fi<<" "<<temp.se<<endl;
int x;
if (temp.fi<=pos){
x=temp.se;
}
else{
temp=root2->query(0,pos);
if (temp.fi==1e9){
bad=true;
break;
}
x=temp.se;
}
root->update(arr[x].fi,2*n,1);
root->update(arr[x].se,2*n,1);
root2->update(arr[x].fi,{1e9,-1});
ans[x]^=1;
}
if (bad || root->query(0,2*n)<0){
cout<<"-1"<<endl;
continue;
}
rep(x,0,n) cout<<ans[x]<<" "; cout<<endl;
}
}
