#include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define fi first #define se second const int N = 1e6+5; int n,cnt1 = 0,cnt2 = 0,check[17][17],cnth[17],cntc[17],ans[N]; pii a[N]; map<int,int>mp1,mp2; void sub2(){ //cout << cnt1 << " " << cnt2 << "\n"; for(int i = 0; i < (1 << n); i++){ for(int j = 1; j <= cnt1; j++){ for(int k = 1; k <= cnt2; k++) check[j][k] = 0; } for(int j = 1; j <= cnt1; j++) cntc[j] = 0; for(int j = 1; j <= cnt2; j++) cnth[j] = 0; for(int bits = 0; bits < n; bits++){ if(i & (1 << bits)){ check[a[bits+1].fi][a[bits+1].se] = 1; //cout << i << " " << a[bits+1].fi << " " << a[bits+1].se << "\n"; cnth[a[bits+1].se]++; cntc[a[bits+1].fi]++; } } //cout << check[1][1] << "\n"; bool ck = true; for(int j = 1; j <= cnt1; j++){ if(cntc[j] > 2){ ck = false; break; } } for(int j = 1; j <= cnt2; j++){ if(cnth[j] > 2){ ck = false; break; } } if(ck == true){ bool lol = true; for(int k = 1; k <= n; k++){ bool ck1 = false; bool ck2 = false; bool ck3 = false; bool ck4 = false; for(int j = 1; j <= a[k].fi; j++){ //cout << i << " " << j << " " << a[k].se << " " << check[j][a[k].se] << "\n"; if(check[j][a[k].se]){ ck1 = true; break; } } for(int j = a[k].fi; j <= cnt1; j++){ if(check[j][a[k].se]){ ck2 = true; break; } } for(int j = 1; j <= a[k].se; j++){ if(check[a[k].fi][j]){ ck3 = true; break; } } for(int j = a[k].se; j <= cnt2; j++){ if(check[a[k].fi][j]){ ck4 = true; break; } } //cout << i << " " << k << " " << ck1 << " " << ck2 << " " << ck3 << " " << ck4 << "\n"; if((ck1 == true && ck2 == true) || (ck3 == true && ck4 == true)) continue; else{ lol = false; break; } } if(lol == true){ for(int bits = 0; bits < n; bits++){ if(i & (1 << bits)) cout << 1; else cout << 0; } return; } } } } vector<pii>adj[N]; void sub3(){ for(int i = 1; i <= n; i++) adj[a[i].se].push_back({a[i].fi,i}); for(int i = 1; i <= cnt2; i++){ sort(adj[i].begin(),adj[i].end()); auto[x,y] = adj[i][0]; auto[x1,y1] = adj[i].back(); ans[y] = 1; ans[y1] = 1; } for(int i = 1; i <= n; i++) cout << ans[i]; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i].fi >> a[i].se; mp1[a[i].fi]++; mp2[a[i].se]++; } for(auto it: mp1) mp1[it.fi] = ++cnt1; for(auto it: mp2) mp2[it.fi] = ++cnt2; for(int i = 1; i <= n; i++){ a[i].fi = mp1[a[i].fi]; a[i].se = mp2[a[i].se]; } if(n <= 16) sub2(); else sub3(); }