Латинские квадраты
| Time limit: | 1 sec. |
| Memory limit: | 262144 KByte |
Латинский квадрат — это таблица N × N, заполненная числами от 1 до N таким образом, чтобы в каждой строке и в каждом столбце встречалось каждое из N чисел.
Пример латинского квадрата 3 × 3:
Дана прямоугольная матрица из чисел W × H (W ≠ H, 2 ≤ W, H ≤ 8). По строкам и столбцам она заполнена числами от 1 до max(W, H). Требуется довести эту матрицу до латинского квадрата со стороной max(W, H) или сообщить, что это невозможно. Запрещается изменять содержимое заданного прямоугольника.
Первая строка во входных данных содержит числа W и H. В последующих H строках записано по W чисел через пробел.
Если довести до латинского квадрата этот прямоугольник нельзя, то выведите «Impossible» (без кавычек), иначе в первой строке выведите длину стороны латинского квадрата, а в следующих строках выведите получившийся латинский квадрат. Числа в столбиках выводите через один пробел. Если решений несколько — выведите любое.
|
Пример ввода 1
3 2
1 2 3
3 1 2
Пример вывода 1
3
1
2 3
3
1 2
2
3 1
|
Пример ввода 2
2 3
1 2
3 1
2 3
Пример вывода 2
3
1
2 3
3
1 2
2
3 1
|
Пример ввода 3
3
2
1
2 3
3
2 1
Пример вывода 3
Impossible
|
|