// Never let them see you bleed...
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 3010, mod = 1e9 + 7, inf = 1e9 + 10;
int a[maxn][maxn];
bool adj[maxn][maxn];
vector<int> vec;
vector<int> comp[maxn];
int C;
bool mark[maxn];
int up[maxn], h[maxn];
int n;
void prep(int u){
mark[u] = 1;
up[u] = h[u];
for(int y = 1; y <= n; y++){
if(!mark[y] && adj[u][y]){
h[y] = h[u] + 1;
prep(y);
up[u] = min(up[u], up[y]);
}
else if(adj[u][y]){
up[u] = min(up[u], h[y]);
}
}
}
void dfs(int u){
mark[u] = 1;
vec.PB(u);
for(int y = 1; y <= n; y++){
if(!mark[y] && adj[u][y]){
int SZ = sz(vec);
dfs(y);
if(up[y] >= h[u]){
while(sz(vec) > SZ){
comp[C].PB(vec.back());
vec.pop_back();
}
comp[C].PB(u);
C++;
}
}
}
}
int pr[maxn];
int fnd(int u){
return pr[u] < 0 ? u : pr[u] = fnd(pr[u]);
}
void mrg(int a, int b){
if((a = fnd(a)) == (b = fnd(b)))
return;
if(pr[a] > pr[b])
swap(a, b);
pr[a]+= pr[b];
pr[b] = a;
}
vector<int> v[maxn];
int ans[maxn];
vector<int> path;
void DFS(int u, int par = -1){
path.PB(u);
if(sz(path) > 2){
int A = a[path[1]][path[sz(path)-1]];
int B = a[path[0]][path[sz(path)-2]];
int C = a[path[1]][path[sz(path)-2]];
int D = a[path[0]][path[sz(path)-1]];
if(A == D && B == D && C == D-1)
mrg(path[0], u);
}
if(sz(path) == 2 && a[path[0]][u] == 1){
mrg(path[0], u);
}
for(int y : v[u]){
if(y != par)
DFS(y, u);
}
path.pop_back();
}
vector<pii> ED;
void adde(int a, int b){
v[a].PB(b);
v[b].PB(a);
ED.PB({a, b});
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
memset(pr, -1, sizeof pr);
int _;
cin >> _;
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin >> a[i][j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(a[i][j] == 1)
mrg(i, j);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(a[i][j] == 2)
adj[fnd(i)][fnd(j)] = 1;
prep(fnd(1));
memset(mark, 0, sizeof mark);
dfs(fnd(1));
assert(sz(vec) == 1);
for(int i = 1; i <= n; i++)
if(fnd(i) != i)
adde(i, fnd(i));
for(int i = 0; i < C; i++)
for(int j = 0; j < sz(comp[i])-1; j++)
adde(comp[i][j], comp[i][j+1]);
memset(pr, -1, sizeof pr);
for(int i = 1; i <= n; i++){
DFS(i);
}
for(int i = 1; i <= n; i++){
cout << fnd(i) << " ";
}
cout << "\n";
for(pii p : ED){
cout << p.F << " " << p.S << "\n";
}
return 0;
}
