Городские олимпиады/1-6 курсы/Межвузовская олимпиада 2015 - командный тур


8. Числа на шахматной доске

Автор задачи: Хаустов Павел
Источник: Региональная олимпиада по программированию 2015, командный тур
Ограничение по времени: 2 с.
Ограничение по памяти: 128 МБ

Имеется обычная шахматная доска размера 8 × 8. В каждую из клеток этой доски Паша записал некоторое число от 1 до 5. Числа были записаны таким образом, чтобы из любой клетки с некоторым числом x можно было добраться до любой другой клетки с тем же числом, совершая переходы только в соседнюю по стороне клетку. Более того, каждое из чисел от 1 до 5 было выписано хотя бы в одну из клеток шахматной доски.

После этого он выписал на листок всепары чисел, которые встречались на соседних по стороне клетках. Паша не стал выписывать пары, в которых оба числа одинаковы.

Миша нашел записи Паши спустя много лет после того, как доска с числами была безнадежно утеряна. Ему стало интересно, как выглядела шахматная доска с числами, для которой Паша выполнил эти записи. Да вот только времени у Миши совсем нет — ему необходимо готовиться к поступлению в Токийский покемонистический университет (ТПУ). За помощью он решил обратиться к Вам.

Напишите программу, которая по информации о выписанных Пашей парах определит какие числа были записаны на шахматной доске, или определит, что Паша ошибся при выполнении своих записей, и не существует ни одного корректного заполнения шахматной доски числами от 1 до 5 описанным образом.

Входные данные

Первая строка входных данных содержит единственное целое число k — количество пар, выписанных Пашей на листок (1 ≤ k ≤ 10).

Далее следует k строк, каждая из которых содержит два целых числа ai и bi — оба числа очередной записанной пары (1 ≤ ai, bi ≤ 5, aibi).

Гарантируется, что пары во входных данных не повторяются, однако числа в парах, как и сами пары, могут следовать в произвольном порядке.

Выходные данные

Если Паша ошибся и не существует ни одного корректного заполнения шахматной доски числами, единственная строка выходных данных должна содержать единственную строку «Incorrect» (без кавычек). Если же корректное заполнение существует, то выходные данные должны содержать восемь строк — по восемь символов каждая. Символ в i-й строке и j-м столбце должен соответствовать числу, которое ставится в клетку шахматной доски в строке i и столбце j.

Примеры
Стандартный вводСтандартный вывод
6
4 3
1 4
1 3
5 2
2 1
3 2
11111111
11444111
11133111
11222221
11222221
11222521
11222221
11111111
2
1 4
2 3
Incorrect