303966: CF763B. Timofey and rectangles

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Timofey and rectangles

题意翻译

- 平面上有n个与坐标轴平行的矩形。矩形的所有边的长度都是奇数。矩形不能相交,但它们可以互相接触。 - 你要让每两个相邻的矩形就会有不同的颜色。输出YES,并给出每个矩形图上的颜色(1,2,3,4)。 - 如果不行输出NO。

题目描述

One of Timofey's birthday presents is a colourbook in a shape of an infinite plane. On the plane $ n $ rectangles with sides parallel to coordinate axes are situated. All sides of the rectangles have odd length. Rectangles cannot intersect, but they can touch each other. Help Timofey to color his rectangles in $ 4 $ different colors in such a way that every two rectangles touching each other by side would have different color, or determine that it is impossible. Two rectangles intersect if their intersection has positive area. Two rectangles touch by sides if there is a pair of sides such that their intersection has non-zero length ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF763B/1e56315d730703e37fe416b7a434283dfefe0bca.png)The picture corresponds to the first example

输入输出格式

输入格式


The first line contains single integer $ n $ ( $ 1<=n<=5·10^{5} $ ) — the number of rectangles. $ n $ lines follow. The $ i $ -th of these lines contains four integers $ x_{1} $ , $ y_{1} $ , $ x_{2} $ and $ y_{2} $ ( $ -10^{9}<=x_{1}&lt;x_{2}<=10^{9} $ , $ -10^{9}<=y_{1}&lt;y_{2}<=10^{9} $ ), that means that points $ (x_{1},y_{1}) $ and $ (x_{2},y_{2}) $ are the coordinates of two opposite corners of the $ i $ -th rectangle. It is guaranteed, that all sides of the rectangles have odd lengths and rectangles don't intersect each other.

输出格式


Print "NO" in the only line if it is impossible to color the rectangles in $ 4 $ different colors in such a way that every two rectangles touching each other by side would have different color. Otherwise, print "YES" in the first line. Then print $ n $ lines, in the $ i $ -th of them print single integer $ c_{i} $ ( $ 1<=c_{i}<=4 $ ) — the color of $ i $ -th rectangle.

输入输出样例

输入样例 #1

8
0 0 5 3
2 -1 5 0
-3 -4 2 -1
-1 -1 2 0
-3 0 0 5
5 2 10 3
7 -3 10 2
4 -2 7 -1

输出样例 #1

YES
1
2
2
3
2
2
4
1

Input

题意翻译

- 平面上有n个与坐标轴平行的矩形。矩形的所有边的长度都是奇数。矩形不能相交,但它们可以互相接触。 - 你要让每两个相邻的矩形就会有不同的颜色。输出YES,并给出每个矩形图上的颜色(1,2,3,4)。 - 如果不行输出NO。

加入题单

上一题 下一题 算法标签: