Triangular Tiling#3082
Triangular domino is a rhombic figure composed of two equilateral triangles.
Similarly, a 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 determine whether it is possible to tile the area with triangular dominoes and triminoes. Each triangle must be covered by exactly one tiling piece.
The first line of the input file contains — the number of triangles in the area (1 \leq n \leq 500). The following lines contain the coordinates of the triangles. The coordinates are assigned to the triangles as shown in the following picture. The absolute values of the coordinates do not exceed .
If tiling is impossible, output "No solution" in the first line of the output file. Otherwise, the first line of the output file must contain — the number of pieces used. Let the pieces be numbered from to , the second line must contain integers: for each triangle in the given area, output the number of the piece that covers it.
Example 1