eolymp
bolt
Try our new interface for solving problems
Problems

Triangular Tiling

Triangular Tiling

Time limit 1 second
Memory limit 256 MiB

Triangular domino is a rhombic figure composed of two equilateral triangles.

Similarly triangular trimino is a trapezoid composed of three equilateral triangles.

Consider a connected area on a triangular grid composed of unit triangles. You have to detect whether it is possible to tile the area with triangular dominoes and triminoes. Each triangle must be covered by exactly one tiling piece.

Input data

The first line of the input file contains n - the number of triangles in the area (1n500). The following n lines contain coordinates of the triangles. The coordinates are assigned to the triangles as shown on the following picture. Coordinates do not exceed 500 by their absolute values.

Output data

If the tiling is impossible, output "No solution" at the first line of the output file. In the other case the first line of the output file must contain k - the number of pieces used. Let the pieces be numbered from 1 to k, the second line must contain n integer numbers, for each triangle of the given area output the number of the piece that it is covered by.

Examples

Input example #1
15
0 0
1 0
2 0
0 1
1 1
2 1
3 1
4 1
-1 2
0 2
1 2
2 2
-2 3
-3 3
-4 3
Output example #1
6
1 1 1 2 2 3 3 3 4 4 5 5 6 6 6
Author Andrew Stankevich
Source Andrew Stankevich Contest 32, Petrozavodsk Summer Training Camp, Wednesday, September 3, 2008