#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1LL;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0LL;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
void sleep(double sec = 1021) {
  clock_t s = clock();
  while (clock() - s < CLOCKS_PER_SEC * sec)
    ;
}
int __ = 1, _cs;
struct DJS {
  int p[30303];
  void init(int n) {
    for (int i = 1; i <= n; i++) p[i] = i;
  }
  int f(int x) { return x == p[x] ? x : p[x] = f(p[x]); }
  void uni(int x, int y) { p[f(x)] = f(y); }
} djs;
int n, k, d[202][30303], who[30303];
void build() {}
void imp() {
  puts("-1");
  exit(0);
}
void init() {
  n = getint();
  k = getint();
  for (int i = 0; i < k; i++) {
    for (int j = 1; j <= n; j++) {
      d[i][j] = getint();
      if (d[i][j] == 0) {
        if (who[i]) imp();
        who[i] = j;
      }
    }
  }
  djs.init(n);
}
set<pair<int, int> > S;
int nd[202][30303], dep[30303];
bool gt[30303];
vector<int> v[30303];
void go(int now, int prt, int tdep) {
  if (dep[now]) imp();
  dep[now] = tdep;
  for (int son : v[now]) {
    if (son == prt) continue;
    go(son, now, tdep + 1);
  }
}
void add_edge(int ai, int bi) {
  if (ai > bi) swap(ai, bi);
  auto it = S.find({ai, bi});
  if (it != S.end()) return;
  if (djs.f(ai) == djs.f(bi)) imp();
  gt[ai] = gt[bi] = true;
  djs.uni(ai, bi);
  S.insert({ai, bi});
  v[ai].push_back(bi);
  v[bi].push_back(ai);
}
void output() {
  for (auto i : S) printf("%d %d\n", i.first, i.second);
  exit(0);
}
vector<pair<int, int> > wt[30303];
void cons(int id) {
  if (wt[id].empty()) return;
  sort(wt[id].begin(), wt[id].end());
  vector<int> dd;
  for (auto i : wt[id]) dd.push_back(i.first);
  dd.resize(unique(dd.begin(), dd.end()) - dd.begin());
  if (dd[0] == 0) imp();
  for (size_t i = 0; i < dd.size(); i++)
    if (dd[i] != (int)i + 1) imp();
  int pre = id;
  for (size_t i = 0; i < wt[id].size(); i++) {
    add_edge(pre, wt[id][i].second);
    if (i + 1 < wt[id].size() and wt[id][i].first != wt[id][i + 1].first)
      pre = wt[id][i].second;
  }
}
void gogo(int id, int now, int prt, int tdep) {
  if (d[id][now] != tdep) imp();
  for (int son : v[now]) {
    if (son == prt) continue;
    gogo(id, son, now, tdep + 1);
  }
}
void recheck() {
  if ((int)S.size() + 1 != n) imp();
  for (int i = 0; i < k; i++) gogo(i, who[i], who[i], 0);
}
void solve2() {
  for (int i = 1; i < k; i++) {
    if (d[0][who[i]] != d[i][who[0]]) imp();
    int dst = d[0][who[i]];
    for (int j = 1; j <= n; j++)
      if (d[0][j] + d[i][j] == dst) {
        if (nd[i][d[0][j]]) imp();
        nd[i][d[0][j]] = j;
      }
    for (int j = 1; j <= dst; j++) {
      if (!nd[i][j]) imp();
      add_edge(nd[i][j - 1], nd[i][j]);
    }
  }
  go(who[0], -1, 1);
  for (int i = 1; i <= n; i++) {
    if (gt[i]) continue;
    int bst = who[0];
    for (int j = 1; j < k; j++) {
      int tmp = who[0];
      int dlt = abs(d[0][i] - d[j][i]);
      if (dlt == d[0][who[j]]) {
        if (d[0][i] > d[j][i]) tmp = who[j];
      } else {
        if (dlt % 2 != d[0][who[j]] % 2) imp();
        dlt = d[j][i] - d[0][i];
        int at = (d[0][who[j]] - dlt) / 2;
        tmp = nd[j][at];
      }
      if (dep[tmp] > dep[bst]) bst = tmp;
    }
    wt[bst].push_back({d[0][i] - dep[bst] + 1, i});
  }
  for (int i = 1; i <= n; i++) cons(i);
  recheck();
  output();
}
void solve() {
  if (k == 1) {
    vector<int> vv;
    for (int i = 1; i <= n; i++) vv.push_back(d[0][i]);
    sort(vv.begin(), vv.end());
    if (vv[0] != 0) imp();
    if (vv[1] == 0) imp();
    vv.resize(unique(vv.begin(), vv.end()) - vv.begin());
    for (size_t i = 0; i < vv.size(); i++)
      if (vv[i] != (int)i) imp();
    vector<pair<int, int> > v2;
    for (int i = 1; i <= n; i++) v2.push_back({d[0][i], i});
    sort(v2.begin(), v2.end());
    int pre = v2[0].second;
    for (size_t i = 1; i < v2.size(); i++) {
      add_edge(pre, v2[i].second);
      if (i + 1 < v2.size() and v2[i].first != v2[i + 1].first)
        pre = v2[i].second;
    }
    output();
  }
  solve2();
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}

### Prompt

Create a solution in CPP for 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>
#pragma GCC optimize("O3")
using namespace std;
inline long long getint() {
  long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline long long add(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline long long sub(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline long long mul(long long _x, long long _y,
                     long long _mod = 1000000007LL) {
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
long long mypow(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 1LL;
  long long _ret = mypow(mul(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = mul(_ret, _a, _mod);
  return _ret;
}
long long mymul(long long _a, long long _x, long long _mod) {
  if (_x == 0) return 0LL;
  long long _ret = mymul(add(_a, _a, _mod), _x >> 1, _mod);
  if (_x & 1) _ret = add(_ret, _a, _mod);
  return _ret;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
void sleep(double sec = 1021) {
  clock_t s = clock();
  while (clock() - s < CLOCKS_PER_SEC * sec)
    ;
}
int __ = 1, _cs;
struct DJS {
  int p[30303];
  void init(int n) {
    for (int i = 1; i <= n; i++) p[i] = i;
  }
  int f(int x) { return x == p[x] ? x : p[x] = f(p[x]); }
  void uni(int x, int y) { p[f(x)] = f(y); }
} djs;
int n, k, d[202][30303], who[30303];
void build() {}
void imp() {
  puts("-1");
  exit(0);
}
void init() {
  n = getint();
  k = getint();
  for (int i = 0; i < k; i++) {
    for (int j = 1; j <= n; j++) {
      d[i][j] = getint();
      if (d[i][j] == 0) {
        if (who[i]) imp();
        who[i] = j;
      }
    }
  }
  djs.init(n);
}
set<pair<int, int> > S;
int nd[202][30303], dep[30303];
bool gt[30303];
vector<int> v[30303];
void go(int now, int prt, int tdep) {
  if (dep[now]) imp();
  dep[now] = tdep;
  for (int son : v[now]) {
    if (son == prt) continue;
    go(son, now, tdep + 1);
  }
}
void add_edge(int ai, int bi) {
  if (ai > bi) swap(ai, bi);
  auto it = S.find({ai, bi});
  if (it != S.end()) return;
  if (djs.f(ai) == djs.f(bi)) imp();
  gt[ai] = gt[bi] = true;
  djs.uni(ai, bi);
  S.insert({ai, bi});
  v[ai].push_back(bi);
  v[bi].push_back(ai);
}
void output() {
  for (auto i : S) printf("%d %d\n", i.first, i.second);
  exit(0);
}
vector<pair<int, int> > wt[30303];
void cons(int id) {
  if (wt[id].empty()) return;
  sort(wt[id].begin(), wt[id].end());
  vector<int> dd;
  for (auto i : wt[id]) dd.push_back(i.first);
  dd.resize(unique(dd.begin(), dd.end()) - dd.begin());
  if (dd[0] == 0) imp();
  for (size_t i = 0; i < dd.size(); i++)
    if (dd[i] != (int)i + 1) imp();
  int pre = id;
  for (size_t i = 0; i < wt[id].size(); i++) {
    add_edge(pre, wt[id][i].second);
    if (i + 1 < wt[id].size() and wt[id][i].first != wt[id][i + 1].first)
      pre = wt[id][i].second;
  }
}
void gogo(int id, int now, int prt, int tdep) {
  if (d[id][now] != tdep) imp();
  for (int son : v[now]) {
    if (son == prt) continue;
    gogo(id, son, now, tdep + 1);
  }
}
void recheck() {
  if ((int)S.size() + 1 != n) imp();
  for (int i = 0; i < k; i++) gogo(i, who[i], who[i], 0);
}
void solve2() {
  for (int i = 1; i < k; i++) {
    if (d[0][who[i]] != d[i][who[0]]) imp();
    int dst = d[0][who[i]];
    for (int j = 1; j <= n; j++)
      if (d[0][j] + d[i][j] == dst) {
        if (nd[i][d[0][j]]) imp();
        nd[i][d[0][j]] = j;
      }
    for (int j = 1; j <= dst; j++) {
      if (!nd[i][j]) imp();
      add_edge(nd[i][j - 1], nd[i][j]);
    }
  }
  go(who[0], -1, 1);
  for (int i = 1; i <= n; i++) {
    if (gt[i]) continue;
    int bst = who[0];
    for (int j = 1; j < k; j++) {
      int tmp = who[0];
      int dlt = abs(d[0][i] - d[j][i]);
      if (dlt == d[0][who[j]]) {
        if (d[0][i] > d[j][i]) tmp = who[j];
      } else {
        if (dlt % 2 != d[0][who[j]] % 2) imp();
        dlt = d[j][i] - d[0][i];
        int at = (d[0][who[j]] - dlt) / 2;
        tmp = nd[j][at];
      }
      if (dep[tmp] > dep[bst]) bst = tmp;
    }
    wt[bst].push_back({d[0][i] - dep[bst] + 1, i});
  }
  for (int i = 1; i <= n; i++) cons(i);
  recheck();
  output();
}
void solve() {
  if (k == 1) {
    vector<int> vv;
    for (int i = 1; i <= n; i++) vv.push_back(d[0][i]);
    sort(vv.begin(), vv.end());
    if (vv[0] != 0) imp();
    if (vv[1] == 0) imp();
    vv.resize(unique(vv.begin(), vv.end()) - vv.begin());
    for (size_t i = 0; i < vv.size(); i++)
      if (vv[i] != (int)i) imp();
    vector<pair<int, int> > v2;
    for (int i = 1; i <= n; i++) v2.push_back({d[0][i], i});
    sort(v2.begin(), v2.end());
    int pre = v2[0].second;
    for (size_t i = 1; i < v2.size(); i++) {
      add_edge(pre, v2[i].second);
      if (i + 1 < v2.size() and v2[i].first != v2[i + 1].first)
        pre = v2[i].second;
    }
    output();
  }
  solve2();
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}

```