写到一半发现标签有二分图就不对劲了，题解区里都是欧拉回路。
然而我是随机化+模拟网络流！自豪
首先可以先建模，观察同一种颜色，发现每一行或每一列的限制即为 \(\lfloor\frac{t}{2}\rfloor\le x\le \lceil\frac{t}{2}\rceil\)。
然后套路地把横坐标和纵坐标分开来建个二分图，建立源点汇点之后连边，发现是个有源汇上下界可行流。
转化为无源汇的可行流之后，考虑模拟网络流。
类似匈牙利算法的那样不断找增广路即可。
但是，发现这样需要增广 \(O(n)\) 次，感觉可能跑步过去。
所以考虑随机化，先随机一个顺序，按顺序加点，直到该点对应的行或列的限制达到了下界。
然后就这么跑过去了……
代码
#include<bits/stdc++.h>
#define Assert(...) if(!(__VA_ARGS__))\
fprintf(stderr,"assert fail: %s",#__VA_ARGS__),exit(0)
using namespace std;
using ll=long long;
const int N=2e5+10,m=2e5;
int n;
struct node{
int x,y;
}a[N];
int cur[N];
mt19937 rnd(time(0));
int ta[N],tb[N],cnta[N],cntb[N];
bool chka(int x){
return ta[x]<=(cnta[x]-1)/2;
}
bool chkb(int y){
return tb[y]<=(cntb[y]-1)/2;
}
bool Chka(int x){
return ta[x]*2+1<cnta[x];
}
bool Chkb(int y){
return tb[y]*2+1<cntb[y];
}
int col[N];
set<int>H[2][N],L[2][N];
void rev1(int i){
if(!col[i])H[col[i]][a[i].x].erase(i);
else L[col[i]][a[i].y].erase(i);
col[i]^=1;
if(!col[i])H[col[i]][a[i].x].insert(i);
else L[col[i]][a[i].y].insert(i);
}
void rev2(int i){
if(col[i])H[col[i]][a[i].x].erase(i);
else L[col[i]][a[i].y].erase(i);
col[i]^=1;
if(col[i])H[col[i]][a[i].x].insert(i);
else L[col[i]][a[i].y].insert(i);
}
bool find1(int);
bool find2(int);
bool find3(int);
bool find4(int);
int t1,t2,s1[N],s2[N],vis1[N],vis2[N];
bool find1(int h){
if(vis1[h])return 0;
s1[++t1]=h,vis1[h]=1;
if(cnta[h]==ta[h]*2-1)return ta[h]--,1;
for(int i:H[0][h]){
if(find2(a[i].y))return rev1(i),1;
}
return 0;
}
bool find2(int l){
if(vis2[l])return 0;
s2[++t2]=l,vis2[l]=1;
if(chkb(l))return tb[l]++,1;
for(int i:L[1][l]){
if(find1(a[i].x))return rev1(i),1;
}
return 0;
}
bool find3(int h){
if(vis1[h])return 0;
s1[++t1]=h,vis1[h]=1;
if(chka(h))return ta[h]++,1;
for(int i:H[1][h]){
if(find4(a[i].y))return rev2(i),1;
}
return 0;
}
bool find4(int l){
if(vis2[l])return 0;
s2[++t2]=l,vis2[l]=1;
if(cntb[l]==tb[l]*2-1)return tb[l]--,1;
for(int i:L[0][l]){
if(find3(a[i].x))return rev2(i),1;
}
return 0;
}
int main(){
freopen(".in","r",stdin);
freopen(".out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
cnta[a[i].x]++,cntb[a[i].y]++;
}
iota(cur,cur+1+n,0),shuffle(cur+1,cur+1+n,rnd);
for(int x=1;x<=n;x++){
int i=cur[x];
if(Chka(a[i].x)&&Chkb(a[i].y)){
col[i]=1,ta[a[i].x]++,tb[a[i].y]++;
}
}
for(int i=1;i<=n;i++){
if(!col[i])H[col[i]][a[i].x].insert(i);
else L[col[i]][a[i].y].insert(i);
}
for(int i=1;i<=m;i++){
for(;Chka(i);){
Assert(find1(i));
ta[i]++;
for(;t1;)vis1[s1[t1--]]=0;
for(;t2;)vis2[s2[t2--]]=0;
}
}
for(int i=1;i<=n;i++){
if(col[i])H[col[i]][a[i].x].insert(i);
else L[col[i]][a[i].y].insert(i);
}
for(int i=1;i<=m;i++){
for(;Chkb(i);){
Assert(find4(i));
tb[i]++;
for(;t1;)vis1[s1[t1--]]=0;
for(;t2;)vis2[s2[t2--]]=0;
}
}
for(int i=1;i<=n;i++)putchar("br"[col[i]]);
cerr<<1.0*clock()/CLOCKS_PER_SEC<<"s\n";
return 0;
}