Дан набор костяшек домино. Можно ли выложить все доминошки в цепочку друг за другом так, что бы любые две соприкасались сторонами с одинаковым числом очков? В наборе может встречаться две и более костяшек одного вида. Костяшки можно переворачивать, меняя левую и правую сторону (костяшка «1-4» превращается в «4-1»).
Выходные данные
Выведите «No solution», если костяшки выложить требуемым образом невозможно. Если решение существует, то опишите любой из способов укладки. Доминошки выкладываются справа налево. В каждой из n строк запишите номер костяшки, которая кладётся в соответствующей позиции, а затем (через пробел) знак «+» (в случае, если доминошку не следует переворачивать) или «–» (если её надо перевернуть).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2
2 4
2 4
6 4
2 1
|
2 -
1 -
5 -
3 +
4 -
|