Треугольная плитка
Треугольное домино — это ромбическая фигура, составленная из двух равносторонних треугольников.
Аналогично, треугольное тримино — это трапеция, состоящая из трех равносторонних треугольников.
Рассмотрим соединенную область на треугольной сетке, состоящую из единичных треугольников. Ваша задача — определить, возможно ли замостить эту область с помощью треугольных домино и тримино. Каждый треугольник должен быть покрыт ровно одной плиткой.
Входные данные
Первая строка входного файла содержит число n — количество треугольников в области (1 ≤ n ≤ 500). Следующие n строк содержат координаты треугольников. Координаты присваиваются треугольникам, как показано на следующем рисунке. Координаты не превышают 500 по абсолютной величине.
Выходные данные
Если замощение невозможно, выведите "No solution" в первой строке выходного файла. В противном случае первая строка выходного файла должна содержать число k — количество использованных плиток. Пусть плитки будут пронумерованы от 1 до k, вторая строка должна содержать n целых чисел, для каждого треугольника данной области укажите номер плитки, которой он покрыт.