//////////////////////////////////////////// _LeMur_
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <chrono>
#include <random>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <ctime>
#include <stack>
#include <queue>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
const int N = 3005;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;
int t;
int n;
int a[N][N];
int parent[N] , cnt[N];
int answ[N];
vector < pair<int,int> > edge;
vector <int> g[N];
int findher(int v){
if(v == parent[v])return v;
return parent[v] = findher(parent[v]);
}
void tmerge(int a,int b){
a = findher(a);
b = findher(b);
if(a == b)return ;
edge.push_back(make_pair(a , b));
g[a].push_back(b);
g[b].push_back(a);
parent[a] = b;
}
bool used[N];
int timer = 0;
void give_color(int st,int v,int p){
if(cnt[ answ[v] ] == 0){
if(a[st][v] == a[st][p]){
answ[st] = answ[v];
}
}
if(p != -1) cnt[ answ[v] ]++;
for(int i=0;i<(int)g[v].size();i++){
int to = g[v][i];
if(used[to] == false || to == p)continue;
give_color(st , to , v);
}
if(p != -1) cnt[ answ[v] ]--;
}
void dfs(int v,int p){
used[v] = true;
give_color(v , v , -1);
if(answ[v] == 0) answ[v] = ++timer;
for(int i=0;i<(int)g[v].size();i++){
int to = g[v][i];
if(to == p)continue;
dfs(to , v);
}
}
int main(){
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
cin >> t;
cin >> n;
for(int i=1;i<=n;i++){
parent[i] = i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
if(i == j)continue;
if(a[i][j] == 1){
tmerge(i , j);
}
}
}
vector <int> vert;
for(int i=1;i<=n;i++){
vert.push_back(findher(i));
}
sort(vert.begin() , vert.end());
vert.resize( unique(vert.begin() , vert.end()) - vert.begin() );
for(int i=0;i<(int)vert.size();i++){
int v1 = vert[i];
for(int j=i + 1;j<(int)vert.size();j++){
int v2 = vert[j];
if(a[v1][v2] == 2){
tmerge(v1 , v2);
}
}
}
cnt[0] = 1;
dfs(1 , 0);
for(int i=1;i<=n;i++){
cout << answ[i] << " ";
}
cout << endl;
for(int i=0;i<n-1;i++){
cout << edge[i].first << " " << edge[i].second << endl;
}
return 0;
}
/*
2
4
1 2 2 2
2 1 2 2
2 2 1 2
2 2 2 1
*/
