# Codeforces Round #345 (Div. 1) C. Table Compression

## 原题

C. Table Compression
time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Little Petya is now fond of data compression algorithms. He has already studied gz, bz, zip algorithms and many others. Inspired by the new knowledge, Petya is now developing the new compression algorithm which he wants to name dis.

Petya decided to compress tables. He is given a table a consisting of n rows and m columns that is filled with positive integers. He wants to build the table a' consisting of positive integers such that the relative order of the elements in each row and each column remains the same. That is, if in some row i of the initial table ai, j < ai, k, then in the resulting table a'i, j < a'i, k, and if ai, j = ai, k then a'i, j = a'i, k. Similarly, if in some column j of the initial table ai, j < ap, j then in compressed table a'i, j < a'p, j and if ai, j = ap, j then a'i, j = a'p, j.

Because large values require more space to store them, the maximum value in a' should be as small as possible.

Petya is good in theory, however, he needs your help to implement the algorithm.

Input

The first line of the input contains two integers n and m (, the number of rows and the number of columns of the table respectively.

Each of the following n rows contain m integers ai, j (1 ≤ ai, j ≤ 109) that are the values in the table.

Output

Output the compressed table in form of n lines each containing m integers.

If there exist several answers such that the maximum number in the compressed table is minimum possible, you are allowed to output any of them.

Examples
input
```2 2
1 2
3 4```
output
```1 2
2 3```
input
```4 3
20 10 30
50 40 30
50 60 70
90 80 70```
output
```2 1 3
5 4 3
5 6 7
9 8 7```
Note

In the first sample test, despite the fact a1, 2 ≠ a21, they are not located in the same row or column so they may become equal after the compression.

## 分析

e[3] = {1} // 代表下标为3的子集大于下标为1的子集（注元素下标我们从1开始计）

e[1] = {2} // 同上

dp[3] = max(1, dp[1] + 1); // 因为3集合要比1集合大，所以我们3集合的最小值为1何dp[1] + 1的其中最大的一个

## 程序范例

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

const int N = 1e6 + 10; // 矩阵中每一个数的上限
int n, m; // n -> 行数 m -> 列数
int ar[N]; // 用一维数组存储原始矩阵数据
int pos[N]; // 存某一行（或者列）的所有元素的索引下标（从1开始记）
int cnt; // n * m
vector<int> e[N]; // 多源有向图，维护集合之间的大小关系
vector<int> se[N]; // 每一个集合的元素
int ans[N]; // 压缩后的矩阵数据
int dp[N]; // 动态规划
int p[N]; // 并查集数组

/**
* 迭代找爹，一直找到祖宗.
*/
int find(int x)
{
return p[x] == x ? p[x] : p[x] = find(p[x]);
}

/**
* 比较函数，正序排序.
*/
bool cmp(int x, int y)
{
return ar[x] < ar[y];
}

/**
* 干活.
*/
void work(int x, int y)
{
// 如果原始矩阵中x和y位置的元素不等，那么让x所在位置的元素值为相对大的那个
if (ar[x] < ar[y]) {
swap(x, y);
}
if (ar[x] == ar[y]) {
// 让并查集的x的祖宗服从y的祖宗
p[find(x)] = find(y);
return;
}
e[x].push_back(y);
}

int dfs(int x)
{
x = find(x);
if (dp[x]) {
return dp[x];
}
dp[x] = 1;
// 独立的子集数
for (int i = 0; i < se[x].size(); i++) {
// 遍历每个子集里面的所有元素，比如子集1里面只有一个元素20
for (int j = 0; j < e[se[x][i]].size(); j++) {
int to = e[se[x][i]][j];
dp[x] = max(dp[x], dfs(to) + 1);
}
}
return dp[x];
}

int main()
{
// 输入行数与列数
cin>>n;
cin>>m;

// 初始化原始矩阵数组
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cnt++;
cin>>ar[cnt];
}
}

// 初始化并查集数组
for (int i = 1; i <= cnt; i++) {
p[i] = i;
}

// 看里面注释
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 在某一行的前提下，取每一列的位置
pos[j] = (i - 1) * m + j;
}
// 将每一行的元素正序排序
sort(pos + 1, pos + 1 + m, cmp);
for (int j = 1; j < m; j++) {
work(pos[j], pos[j + 1]);
}
}

// 遍历所有每一行的元素
for (int j = 1; j <= m; j++) {
// 获取每一行的元素，pos的值为数组索引
for (int i = 1; i <= n; i++) {
pos[i] = (i - 1) * m + j;
}
sort(pos + 1, pos + 1 + n, cmp);
// 进行并查集运算，处理p数组，分成若干子集合，同时建立多元有向图集合e（用于维护哪个集合和哪个集合的大小关系）
for (int i = 1; i < n; i++) {
work(pos[i], pos[i + 1]);
}
}

// 获取每个集合里面的所有元素
for (int i = 1; i <= cnt; i++) {
int fa = find(i);
se[fa].push_back(i);
}

// 计算结果，利用动态规划的思想。即当前元素x的最小值，为max(1, dp[x - 1])。
// 其中x - 1 即为 e[x]的值
for (int i = 1; i <= cnt; i++) {
ans[i] = dfs(i);
}

// 输出结果
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout<<ans[(i - 1) * m + j]<<' ';
}
cout<<endl;
}

return 0;
}
```