| Codeforces Round 345 (Div. 1) |
|---|
| Закончено |
Петя увлёкся алгоритмами сжатия данных. Он уже изучил форматы gz, bz, zip и несколько других. Воодушевившись новыми знаниями, Петя собрался разработать свой формат сжатия и назвать его dis.
Петя решил сжимать таблицы. У него есть таблица, состоящая из n строк и m столбцов, заполненная целыми положительными числами. Он хочет заменить значения элементов таблицы на целые положительные числа так, чтобы отношение элементов в каждой строке и каждом столбце не изменилось. То есть, если в некоторой строке исходной таблицы ai, j < ai, k, то и в сжатой таблице a'i, j < a'i, k, и если ai, j = ai, k, то a'i, j = a'i, k. Аналогично, если в некотором столбце исходной таблицы ai, j < ap, j, то и в сжатой таблице a'i, j < a'p, j, и если ai, j = ap, j, то a'i, j = a'p, j.
Поскольку большие значения требуют больше места для хранения, максимальное значение элемента получившейся матрицы должно быть как можно меньше.
В теории Петя мастер, но вот писать код он не любит. Помогите ему реализовать формат сжатия dis.
В первой строке входных данных содержатся два числа n и m (
— количество строк и столбцов таблицы соответственно.
В следующих n строках содержится по m целых чисел ai, j (1 ≤ ai, j ≤ 109) — значения элементов таблицы.
Выведите сжатую таблицу: n строк, содержащих по m чисел.
Если существует несколько ответов, минимизирующих максимальное число, то разрешается вывести любой из них.
2 2
1 2
3 4
1 2
2 3
4 3
20 10 30
50 40 30
50 60 70
90 80 70
2 1 3
5 4 3
5 6 7
9 8 7
В первом примере a1, 2 ≠ a2, 1, но, поскольку они не располагаются в одной строке или в одном столбце, при сжатии их можно сделать равными.
