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

Латинські квадрати

Латинські квадрати

Латинський квадрат --- це таблиця \textbf{N}×\textbf{N}, заповнена числами від \textbf{1} до \textbf{N} таким чином, щоб у кожному рядку і у кожному стовбці зустрічалось кожне з \textbf{N} чисел. Приклад латинського квадрату \textbf{3}×\textbf{3}: Задано прямокутну матрицю з чисел \textbf{W}×\textbf{H} (\textbf{W} ≠ \textbf{H}, \textbf{2} ≤ \textbf{W}, \textbf{H} ≤ \textbf{8}). По рядкам і стовбцям вона заповнена числами від \textbf{1} до \textbf{max}(\textbf{W}, \textbf{H}). Потрібно довести цю матрицю до латинського квадрату зі стороною \textbf{max}(\textbf{W}, \textbf{H}) або повідомити, що це неможливо. Забороняється змінювати вміст заданого прямокутника. \InputFile Перший рядок у вхідних даних містить числа \textbf{W} і \textbf{H}. У наступних \textbf{H} рядках записано по \textbf{W} чисел через пропуск. \OutputFile Якщо довести до латинского квадрату цей прямокутник неможливо, то виведіть "\textbf{Impossible}" (без лапок), інакше у першому рядку виведіть довжину сторони латинського квадрату, а у наступних рядках виведіть отриманий латинський квадрат. Числа у стовбцях виводьте через один пропуск. Якщо розв'язків декілька --- виведіть довільний.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
3 2
1 2 3
3 1 2
Вихідні дані #1
3
1 2 3
3 1 2
2 3 1
Джерело Китеня 2011 м. Ковров