<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

425. Control function
Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



A matrix T of non-negative integers with n rows and m columns is called a control matrix when its first row is different from all other rows. Formally speaking,   T1j ≠ Tij.

A function f from non-negative integers to non-negative integers is called a control function for the given control matrix T when the matrix f(T) obtained by applying f to every element of T is also a control matrix. Formally speaking,   f(T1j) ≠ f(Tij).

Find a control function with all values not exceeding 50 for the given control matrix T.

Input
The first line of the input file contains two integers n and m (1 ≤ n, m ≤ 1000). The next n lines contain m integers each, representing the matrix Tij (). It is guaranteed that the matrix T is a control matrix.

Output
Output "Yes" (without quotes) to the first line of the output file if such a function exists, and "No" (without quotes) otherwise. If the answer is positive, then output the function via "key -> value" pairs (without quotes). Order keys in increasing order. All different numbers from matrix T must appear as a key exactly once, and no other keys should be printed.

Example(s)
sample input
sample output
1 5
1 2 3 4 5
Yes
1 -> 0
2 -> 0
3 -> 0
4 -> 0
5 -> 0

sample input
sample output
2 2
1 2
1 3
Yes
1 -> 1
2 -> 1
3 -> 0

sample input
sample output
4 2
0 2
4 5
7 6
3 1
Yes
0 -> 1
1 -> 0
2 -> 1
3 -> 0
4 -> 1
5 -> 0
6 -> 1
7 -> 0

<|response|>
## 1) Abridged problem statement (concise)

You are given an `n × m` matrix `T` of non‑negative integers (`1 ≤ n,m ≤ 1000`). It is guaranteed that for every row `i > 1`, row `i` differs from the first row in at least one column.

Define a function `f : ℕ → ℕ`. After applying `f` to every matrix element, the first row must still differ from every other row (i.e., for each `i>1` there exists a column `j` with `f(T[1][j]) ≠ f(T[i][j])`).

Construct such a function where **all produced values are ≤ 50**, and output `f(x)` for every **distinct** number `x` appearing in `T`, as `x -> f(x)` in increasing order of `x`. Print `"No"` if impossible.

---

## 2) Key observations

1. **You only need one surviving mismatch per row.**  
   For each row `i>1`, it suffices that *some* column where `T[i][j] ≠ T[1][j]` remains different after mapping.

2. **Turn the task into “must be different” constraints between values.**  
   For each row `i>1`, pick **one** column `j` where it differs from row 1 (e.g., the first such `j`). Then we must enforce:
   \[
   f(T[i][j]) \ne f(T[1][j]).
   \]
   This is a single inequality constraint between two values from the matrix.

3. **Model constraints as a graph coloring problem.**  
   - Vertices: distinct values in the matrix.
   - Edge `(u,v)`: means `f(u) != f(v)`.

   If we properly color this graph, using the color as `f(value)`, all constraints are satisfied.

4. **There are few edges, so few colors suffice.**  
   We add at most one edge per row `i>1`, so:
   \[
   E \le n-1 \le 999.
   \]
   Graphs with at most 999 edges can be greedily colored using **< 50** colors (a known bound is `≤ ⌊√(2E)⌋ + 1`, and `√(2·999) ≈ 44.7`).

5. **Values not in any constraint can map to 0.**  
   Only vertices that appear in at least one edge need a positive color; all others can be safely assigned `0`.

---

## 3) Full solution approach

### Step A: Read input and collect all distinct values
- Read the matrix.
- Gather all numbers, sort, unique → list `vals` (these are the keys you must output).

### Step B: Build the constraint graph
For each row `i = 2..n`:
- Find the first column `j` such that `T[i][j] != T[1][j]`.
- Add an undirected edge between:
  - `u = T[i][j]`
  - `v = T[1][j]`

This ensures that after mapping, row `i` still differs from row 1 at that chosen column.

### Step C: Greedy color the graph (values → colors 1..)
- Consider only vertices with positive degree (appear in constraints).
- Process vertices in increasing degree order (helps keep colors small).
- For each vertex, choose the smallest positive color not used by its already-colored neighbors.

This yields a proper coloring with < 50 colors under the constraints above.

### Step D: Output the function
- Print `"Yes"`.
- For each value `x` in `vals` (in increasing order):
  - if `x` is colored: print `x -> color[x]`
  - else: print `x -> 0`

**Complexity**
- Building constraints: worst-case `O(nm)` to find mismatch per row (≤ 1e6 operations).
- Coloring: `O(E + V)` up to log factors (very small here).
- Fits easily within limits.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;
vector<vector<int>> tbl;

void read() {
    cin >> n >> m;
    tbl.assign(n, vector<int>(m, 0));
    cin >> tbl;
}

void solve() {
    // One of the main observations in this problem is that we want to use
    // values <= 50. This is an interesting value, and particularly, it's
    // O(sqrt(N)). We should keep this in mind.
    //
    // Often in problems like this, it's useful to either find cases where the
    // answer is No, or figure out why the answer is always Yes. It's hard to
    // find cases where it's important, as for one, N should be > 50, so it
    // should suggest us to try figuring how to always construct a table with 50
    // as the largest value. The worst case for us would be if every row matches
    // in exactly one column with the first one, as it eliminates the
    // optionality. Hence, we can consider the case where there is only 1
    // mismatch per row, and we want to choose <= 50 values such that the
    // mismatches per row aren't mapped to the same value. This should remind us
    // of a famous graph theory problem - the graph coloring. Essentially, every
    // value is a vertex and we have N - 1 edges (the mismatches), and we want
    // to choose <= 50 colors. The simple greedy algorithm of going in
    // increasing order of degrees achieves this O(sqrt(edges)) bound on number
    // of colors. It's fairly easy to prove, but here is also a link for this:
    //
    // https://math.stackexchange.com/questions/4114699/graph-coloring-why-is-fm-leq-sqrtm
    //
    // We can remember the initial observation we had: sqrt(n-1) is well below
    // the 50 bound we had, so this solution should work. The only case left is
    // when there are 2 or more mismatches between row 1 and some other row. We
    // briefly mentioned it above, but this just gives us more optionality, so
    // we can just leave one of the two possible edges randomly, as the greedy
    // guarantees we can color with sqrt(edges) colors.

    vector<int> values;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            values.push_back(tbl[i][j]);
        }
    }

    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());

    map<int, vector<int>> adj;
    map<int, int> degree, colors;

    for(int i = 1; i < n; i++) {
        for(int j = 0; j < m; j++) {
            int u = tbl[i][j], v = tbl[0][j];
            if(u != v) {
                degree[u]++;
                degree[v]++;
                adj[u].push_back(v);
                adj[v].push_back(u);
                break;
            }
        }
    }

    vector<pair<int, int>> vertices;
    for(auto [v, d]: degree) {
        vertices.push_back({d, v});
    }

    sort(vertices.begin(), vertices.end());

    for(auto [d, v]: vertices) {
        set<int> used = {0};
        for(int u: adj[v]) {
            if(colors.count(u)) {
                used.insert(colors[u]);
            }
        }
        int c = 1;
        while(used.count(c)) {
            c++;
        }
        colors[v] = c;
    }

    cout << "Yes\n";
    for(int v: values) {
        auto it = colors.find(v);
        cout << v << " -> ";
        if(it == colors.end()) {
            cout << "0\n";
        } else {
            cout << it->second << '\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys
from collections import defaultdict

def solve() -> None:
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    n = int(next(it))
    m = int(next(it))

    # Read matrix
    tbl = [[int(next(it)) for _ in range(m)] for _ in range(n)]

    # Collect all distinct values (keys that must be printed), sorted
    vals = sorted({tbl[i][j] for i in range(n) for j in range(m)})

    # Build constraint graph from one mismatch per row i>0
    adj = defaultdict(list)
    deg = defaultdict(int)

    for i in range(1, n):
        # find first mismatch with row 0
        for j in range(m):
            u = tbl[i][j]
            v = tbl[0][j]
            if u != v:
                adj[u].append(v)
                adj[v].append(u)
                deg[u] += 1
                deg[v] += 1
                break

    # Vertices involved in constraints, sorted by increasing degree
    vertices = sorted((d, v) for v, d in deg.items())

    # Greedy coloring: color[value] = smallest positive integer not used by colored neighbors
    color = {}

    for _, v in vertices:
        used = set()
        for u in adj[v]:
            if u in color:
                used.add(color[u])

        c = 1
        while c in used:
            c += 1
        color[v] = c
        # With E <= 999, this stays < 50 in this construction.

    # Output
    out = ["Yes"]
    for x in vals:
        out.append(f"{x} -> {color.get(x, 0)}")

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    solve()
```

This construction guarantees that for every row `i>1`, at least one chosen mismatch remains a mismatch after applying `f`, so the transformed matrix is still a control matrix, with all outputs ≤ 50.