eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Triangular Tiling

Triangular Tiling

Ліміт часу 1 секунда
Ліміт використання пам'яті 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.

Вхідні дані

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.

Вихідні дані

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.

Приклад

Вхідні дані #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
Вихідні дані #1
6
1 1 1 2 2 3 3 3 4 4 5 5 6 6 6
Автор Andrew Stankevich
Джерело Andrew Stankevich Contest 32, Petrozavodsk Summer Training Camp, Wednesday, September 3, 2008