#include <bits/stdc++.h>
void solve(std::vector<int32_t>& bucket, bool* important,
           int32_t** important_dist, std::vector<int32_t>* result, int32_t root,
           int32_t external_important) {
  std::vector<int32_t> important_cur;
  for (int32_t i = 0; i < bucket.size(); i++)
    if (important[bucket[i]]) important_cur.push_back(bucket[i]);
  if (important_cur.size() > 0) {
    int32_t simple_path_length;
    std::vector<int32_t> simple_path;
    if (root == -1) {
      if (important_cur.size() > 1) {
        simple_path_length =
            important_dist[important_cur[0]][important_cur[1]] + 1;
        for (int32_t i = 0; i < bucket.size(); i++) {
          int32_t delta = important_dist[important_cur[0]][bucket[i]] +
                          important_dist[important_cur[1]][bucket[i]] -
                          important_dist[important_cur[0]][important_cur[1]];
          if (delta % 2 == 1) {
            std::cout << -1;
            exit(0);
          }
          if (delta == 0) simple_path.push_back(bucket[i]);
        }
      } else {
        std::sort(bucket.begin(), bucket.end(),
                  [important_cur, important_dist](int32_t v1, int32_t v2) {
                    return important_dist[important_cur[0]][v1] <
                           important_dist[important_cur[0]][v2];
                  });
        int32_t active = 0;
        for (int32_t i = 1; i < bucket.size(); i++) {
          if (important_dist[important_cur[0]][bucket[i - 1]] !=
              important_dist[important_cur[0]][bucket[i]])
            active = i - 1;
          result[bucket[active]].push_back(bucket[i]);
          result[bucket[i]].push_back(bucket[active]);
        }
        return;
      }
    } else {
      simple_path_length = important_dist[important_cur[0]][root] + 1;
      for (int32_t i = 0; i < bucket.size(); i++) {
        int32_t delta = important_dist[important_cur[0]][bucket[i]] +
                        important_dist[external_important][bucket[i]] -
                        important_dist[important_cur[0]][external_important];
        if (delta % 2 == 1) {
          std::cout << -1;
          exit(0);
        }
        if (delta == 0) simple_path.push_back(bucket[i]);
      }
      simple_path.push_back(root);
    }
    std::vector<int32_t>* buckets =
        new std::vector<int32_t>[simple_path_length];
    std::sort(simple_path.begin(), simple_path.end(),
              [important_dist, important_cur](int32_t v1, int32_t v2) {
                return important_dist[important_cur[0]][v1] <
                       important_dist[important_cur[0]][v2];
              });
    for (int32_t i = 1; i < simple_path.size(); i++) {
      result[simple_path[i - 1]].push_back(simple_path[i]);
      result[simple_path[i]].push_back(simple_path[i - 1]);
    }
    for (int32_t i = 0; i < bucket.size(); i++) {
      int32_t paired = (root == -1 && important_cur.size() > 1)
                           ? important_cur[1]
                           : external_important;
      int32_t delta = important_dist[important_cur[0]][bucket[i]] +
                      important_dist[paired][bucket[i]] -
                      important_dist[important_cur[0]][paired];
      if (delta % 2 == 1) {
        std::cout << -1;
        exit(0);
      }
      if (delta > 0) {
        if (delta / 2 == simple_path_length - 1 +
                             important_dist[important_cur[0]][bucket[i]])
          buckets[simple_path_length - 1].push_back(bucket[i]);
        else if (important_dist[important_cur[0]][bucket[i]] == delta / 2)
          buckets[0].push_back(bucket[i]);
        else
          buckets[important_dist[important_cur[0]][bucket[i]] - delta / 2]
              .push_back(bucket[i]);
      }
    }
    for (int32_t i = 0; i < simple_path_length; i++) {
      solve(buckets[i], important, important_dist, result, simple_path[i],
            important_cur[0]);
      for (int32_t j = 0; j < buckets[i].size(); j++) {
        int32_t paired = (root == -1 && important_cur.size() > 1)
                             ? important_cur[1]
                             : external_important;
        int32_t delta = important_dist[important_cur[0]][buckets[i][j]] +
                        important_dist[paired][buckets[i][j]] -
                        important_dist[important_cur[0]][paired];
        if (delta == 2) {
          result[simple_path[i]].push_back(buckets[i][j]);
          result[buckets[i][j]].push_back(simple_path[i]);
        }
      }
    }
  } else {
    std::sort(bucket.begin(), bucket.end(),
              [important_dist, external_important](int32_t v1, int32_t v2) {
                return important_dist[external_important][v1] <
                       important_dist[external_important][v2];
              });
    int32_t active = 0;
    for (int32_t i = 1; i < bucket.size(); i++) {
      if (important_dist[external_important][bucket[active]] ==
          important_dist[external_important][bucket[i]] - 2) {
        active = i - 1;
      }
      if (important_dist[external_important][bucket[active]] ==
          important_dist[external_important][bucket[i]] - 1) {
        result[bucket[active]].push_back(bucket[i]);
        result[bucket[i]].push_back(bucket[active]);
      }
    }
  }
}
void dfs(int32_t v, int32_t parent, bool* visited_arr,
         std::vector<int32_t>* tree, int32_t depth, int32_t* expected,
         int32_t& visited) {
  visited++;
  if (depth != expected[v]) {
    std::cout << -1;
    exit(0);
  }
  visited_arr[v] = true;
  for (int32_t i = 0; i < tree[v].size(); i++)
    if (!visited_arr[tree[v][i]]) {
      dfs(tree[v][i], v, visited_arr, tree, depth + 1, expected, visited);
    } else {
      if (tree[v][i] != parent) {
        std::cout << -1;
        exit(0);
      }
    }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  int32_t n, k;
  std::cin >> n >> k;
  int32_t** important_dist = new int32_t*[n];
  bool* important = new bool[n];
  for (int32_t i = 0; i < n; i++) important[i] = false;
  for (int32_t i = 0; i < k; i++) {
    int32_t* important_dist_cur = new int32_t[n];
    int32_t vert = -1;
    for (int32_t j = 0; j < n; j++) {
      std::cin >> important_dist_cur[j];
      if (important_dist_cur[j] == 0) vert = j;
    }
    if (vert == -1) {
      std::cout << -1;
      return 0;
    }
    important[vert] = true;
    important_dist[vert] = important_dist_cur;
  }
  std::vector<int32_t> bucket;
  for (int32_t i = 0; i < n; i++) bucket.push_back(i);
  std::vector<int32_t>* res = new std::vector<int32_t>[n];
  solve(bucket, important, important_dist, res, -1, -1);
  for (int32_t i = 0; i < n; i++) {
    std::sort(res[i].begin(), res[i].end());
    res[i].resize(std::unique(res[i].begin(), res[i].end()) - res[i].begin());
  }
  int32_t total_edges = 0;
  bool* visited_arr = new bool[n];
  for (int32_t i = 0; i < n; i++) {
    total_edges += res[i].size();
    if (important[i]) {
      int32_t visited = 0;
      for (int32_t j = 0; j < n; j++) visited_arr[j] = false;
      dfs(i, -1, visited_arr, res, 0, important_dist[i], visited);
      if (visited != n) {
        std::cout << -1 << "\n";
        return 0;
      }
    }
  }
  if (total_edges / 2 != n - 1) {
    std::cout << -1 << "\n";
    return 0;
  }
  for (int32_t i = 0; i < n; i++) {
    for (int32_t j = 0; j < res[i].size(); j++) {
      if (i < res[i][j]) {
        std::cout << i + 1 << " " << res[i][j] + 1 << "\n";
      }
    }
  }
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

Petya had a tree consisting of n vertices numbered with integers from 1 to n. Accidentally he lost his tree. 

Petya remembers information about k vertices: distances from each of them to each of the n tree vertices.

Your task is to restore any tree that satisfies the information that Petya remembers or report that such tree doesn't exist.

Input

The first line contains two integers n and k (2 ≤ n ≤ 30 000, 1 ≤ k ≤ min(200, n)) — the number of vertices in the tree and the number of vertices about which Petya remembers distance information.

The following k lines contain remembered information. The i-th line contains n integers di, 1, di, 2, ..., di, n (0 ≤ di, j ≤ n - 1), where di, j — the distance to j-th vertex from the i-th vertex that Petya remembers.

Output

If there are no suitable trees, print -1.

In the other case, print n - 1 lines: each line should contain two vertices connected by edge in the required tree. You can print edges and vertices in an edge in any order. The tree vertices are enumerated from 1 to n.

If there are many solutions print any of them.

Examples

Input

5 2
0 1 2 3 2
2 1 0 1 2


Output

2 1
3 2
4 3
5 2


Input

3 1
1 2 1


Output

-1

Note

Picture for the first sample:

<image>

### Response

```cpp
#include <bits/stdc++.h>
void solve(std::vector<int32_t>& bucket, bool* important,
           int32_t** important_dist, std::vector<int32_t>* result, int32_t root,
           int32_t external_important) {
  std::vector<int32_t> important_cur;
  for (int32_t i = 0; i < bucket.size(); i++)
    if (important[bucket[i]]) important_cur.push_back(bucket[i]);
  if (important_cur.size() > 0) {
    int32_t simple_path_length;
    std::vector<int32_t> simple_path;
    if (root == -1) {
      if (important_cur.size() > 1) {
        simple_path_length =
            important_dist[important_cur[0]][important_cur[1]] + 1;
        for (int32_t i = 0; i < bucket.size(); i++) {
          int32_t delta = important_dist[important_cur[0]][bucket[i]] +
                          important_dist[important_cur[1]][bucket[i]] -
                          important_dist[important_cur[0]][important_cur[1]];
          if (delta % 2 == 1) {
            std::cout << -1;
            exit(0);
          }
          if (delta == 0) simple_path.push_back(bucket[i]);
        }
      } else {
        std::sort(bucket.begin(), bucket.end(),
                  [important_cur, important_dist](int32_t v1, int32_t v2) {
                    return important_dist[important_cur[0]][v1] <
                           important_dist[important_cur[0]][v2];
                  });
        int32_t active = 0;
        for (int32_t i = 1; i < bucket.size(); i++) {
          if (important_dist[important_cur[0]][bucket[i - 1]] !=
              important_dist[important_cur[0]][bucket[i]])
            active = i - 1;
          result[bucket[active]].push_back(bucket[i]);
          result[bucket[i]].push_back(bucket[active]);
        }
        return;
      }
    } else {
      simple_path_length = important_dist[important_cur[0]][root] + 1;
      for (int32_t i = 0; i < bucket.size(); i++) {
        int32_t delta = important_dist[important_cur[0]][bucket[i]] +
                        important_dist[external_important][bucket[i]] -
                        important_dist[important_cur[0]][external_important];
        if (delta % 2 == 1) {
          std::cout << -1;
          exit(0);
        }
        if (delta == 0) simple_path.push_back(bucket[i]);
      }
      simple_path.push_back(root);
    }
    std::vector<int32_t>* buckets =
        new std::vector<int32_t>[simple_path_length];
    std::sort(simple_path.begin(), simple_path.end(),
              [important_dist, important_cur](int32_t v1, int32_t v2) {
                return important_dist[important_cur[0]][v1] <
                       important_dist[important_cur[0]][v2];
              });
    for (int32_t i = 1; i < simple_path.size(); i++) {
      result[simple_path[i - 1]].push_back(simple_path[i]);
      result[simple_path[i]].push_back(simple_path[i - 1]);
    }
    for (int32_t i = 0; i < bucket.size(); i++) {
      int32_t paired = (root == -1 && important_cur.size() > 1)
                           ? important_cur[1]
                           : external_important;
      int32_t delta = important_dist[important_cur[0]][bucket[i]] +
                      important_dist[paired][bucket[i]] -
                      important_dist[important_cur[0]][paired];
      if (delta % 2 == 1) {
        std::cout << -1;
        exit(0);
      }
      if (delta > 0) {
        if (delta / 2 == simple_path_length - 1 +
                             important_dist[important_cur[0]][bucket[i]])
          buckets[simple_path_length - 1].push_back(bucket[i]);
        else if (important_dist[important_cur[0]][bucket[i]] == delta / 2)
          buckets[0].push_back(bucket[i]);
        else
          buckets[important_dist[important_cur[0]][bucket[i]] - delta / 2]
              .push_back(bucket[i]);
      }
    }
    for (int32_t i = 0; i < simple_path_length; i++) {
      solve(buckets[i], important, important_dist, result, simple_path[i],
            important_cur[0]);
      for (int32_t j = 0; j < buckets[i].size(); j++) {
        int32_t paired = (root == -1 && important_cur.size() > 1)
                             ? important_cur[1]
                             : external_important;
        int32_t delta = important_dist[important_cur[0]][buckets[i][j]] +
                        important_dist[paired][buckets[i][j]] -
                        important_dist[important_cur[0]][paired];
        if (delta == 2) {
          result[simple_path[i]].push_back(buckets[i][j]);
          result[buckets[i][j]].push_back(simple_path[i]);
        }
      }
    }
  } else {
    std::sort(bucket.begin(), bucket.end(),
              [important_dist, external_important](int32_t v1, int32_t v2) {
                return important_dist[external_important][v1] <
                       important_dist[external_important][v2];
              });
    int32_t active = 0;
    for (int32_t i = 1; i < bucket.size(); i++) {
      if (important_dist[external_important][bucket[active]] ==
          important_dist[external_important][bucket[i]] - 2) {
        active = i - 1;
      }
      if (important_dist[external_important][bucket[active]] ==
          important_dist[external_important][bucket[i]] - 1) {
        result[bucket[active]].push_back(bucket[i]);
        result[bucket[i]].push_back(bucket[active]);
      }
    }
  }
}
void dfs(int32_t v, int32_t parent, bool* visited_arr,
         std::vector<int32_t>* tree, int32_t depth, int32_t* expected,
         int32_t& visited) {
  visited++;
  if (depth != expected[v]) {
    std::cout << -1;
    exit(0);
  }
  visited_arr[v] = true;
  for (int32_t i = 0; i < tree[v].size(); i++)
    if (!visited_arr[tree[v][i]]) {
      dfs(tree[v][i], v, visited_arr, tree, depth + 1, expected, visited);
    } else {
      if (tree[v][i] != parent) {
        std::cout << -1;
        exit(0);
      }
    }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  std::cout.tie(0);
  int32_t n, k;
  std::cin >> n >> k;
  int32_t** important_dist = new int32_t*[n];
  bool* important = new bool[n];
  for (int32_t i = 0; i < n; i++) important[i] = false;
  for (int32_t i = 0; i < k; i++) {
    int32_t* important_dist_cur = new int32_t[n];
    int32_t vert = -1;
    for (int32_t j = 0; j < n; j++) {
      std::cin >> important_dist_cur[j];
      if (important_dist_cur[j] == 0) vert = j;
    }
    if (vert == -1) {
      std::cout << -1;
      return 0;
    }
    important[vert] = true;
    important_dist[vert] = important_dist_cur;
  }
  std::vector<int32_t> bucket;
  for (int32_t i = 0; i < n; i++) bucket.push_back(i);
  std::vector<int32_t>* res = new std::vector<int32_t>[n];
  solve(bucket, important, important_dist, res, -1, -1);
  for (int32_t i = 0; i < n; i++) {
    std::sort(res[i].begin(), res[i].end());
    res[i].resize(std::unique(res[i].begin(), res[i].end()) - res[i].begin());
  }
  int32_t total_edges = 0;
  bool* visited_arr = new bool[n];
  for (int32_t i = 0; i < n; i++) {
    total_edges += res[i].size();
    if (important[i]) {
      int32_t visited = 0;
      for (int32_t j = 0; j < n; j++) visited_arr[j] = false;
      dfs(i, -1, visited_arr, res, 0, important_dist[i], visited);
      if (visited != n) {
        std::cout << -1 << "\n";
        return 0;
      }
    }
  }
  if (total_edges / 2 != n - 1) {
    std::cout << -1 << "\n";
    return 0;
  }
  for (int32_t i = 0; i < n; i++) {
    for (int32_t j = 0; j < res[i].size(); j++) {
      if (i < res[i][j]) {
        std::cout << i + 1 << " " << res[i][j] + 1 << "\n";
      }
    }
  }
  return 0;
}

```