Mike and Fish
题目链接
题意
已知 个点，你需要给每个点红蓝染色，使得每行每列红蓝点数量之差不超过 。
输出一种方案即可。
Description
As everyone knows, bears love fish. But Mike is a strange bear; He hates fish! The even more strange thing about him is he has an infinite number of blue and red fish.
He has marked n distinct points in the plane. i-th point is point (xi, yi). He wants to put exactly one fish in each of these points such that the difference between the number of red fish and the blue fish on each horizontal or vertical line is at most 1.
He can't find a way to perform that! Please help him.
The first line of input contains integer n (1 ≤ n ≤ 2 × 105).
The next n lines contain the information about the points, i-th line contains two integers xi and yi (1 ≤ xi, yi ≤ 2 × 105), the i-th point coordinates.
It is guaranteed that there is at least one valid answer.
Print the answer as a sequence of n characters 'r' (for red) or 'b' (for blue) where i-th character denotes the color of the fish in the i-th point.
Input
The first line of input contains integer n (1 ≤ n ≤ 2 × 105).
The next n lines contain the information about the points, i-th line contains two integers xi and yi (1 ≤ xi, yi ≤ 2 × 105), the i-th point coordinates.
It is guaranteed that there is at least one valid answer.
Output
Print the answer as a sequence of n characters 'r' (for red) or 'b' (for blue) where i-th character denotes the color of the fish in the i-th point.
Samples
4
1 1
1 2
2 1
2 2
brrb
3
1 1
1 2
2 1
brr