#include <bits/stdc++.h>
using namespace std;
using ll = long long;
class DSU{
int n;
vector<int> parent, sz;
public:
DSU(int _n):n(_n), parent(_n), sz(_n, 1){
iota(parent.begin(), parent.end(), 0);
}
void reset(){
iota(parent.begin(), parent.end(), 0);
fill(sz.begin(), sz.end(), 1);
}
int find(int x){
if(x!=parent[x]){
parent[x]=find(parent[x]);
}
return parent[x];
}
bool unite(int x, int y){
x=find(x);
y=find(y);
if(x==y)return false;
if(sz[x]<sz[y])swap(x, y);
parent[y]=x;
sz[x]+=sz[y];
return true;
}
bool same(int x, int y){
return find(x)==find(y);
}
int size(int x){
return sz[find(x)];
}
};
void solve() {
int _;
cin >> _;
int n;
cin >> n;
vector<vector<int>> g(n, vector<int>(n, 0));
DSU dsu(n);
for(int i=0; i<n; i++)
for(int j=0; j<n; j++){
cin >> g[i][j];
if(g[i][j]==1) dsu.unite(i, j);
}
vector<int> id(n, -1);
vector<vector<int>> comp;
for(int i=0; i<n; i++) {
int r = dsu.find(i);
if(id[r]==-1) {
id[r] = (int)comp.size();
comp.push_back({});
}
comp[id[r]].push_back(i);
}
vector<int> root(n, -1);
int idx = 0;
for(int i=0; i<n; i++)
if(dsu.find(i)==i)
if(root[i]==-1)
root[i] = idx++;
vector<int> rep(n, -1);
for(int i=0; i<n; i++) rep[i] = dsu.find(i);
unordered_map<int, int> mp;
mp.reserve(n<<1);
comp.clear();
for(int i=0; i<n; i++){
int rroot = rep[i];
if(mp.find(rroot)==mp.end()) {
int idd = (int)comp.size();
mp[rroot]=idd;
comp.push_back({});
}
comp[mp[rroot]].push_back(i);
}
int m = (int)comp.size();
for(int i=0; i<m; i++) rep[i] = comp[i][0];
if(m==1) {
for(int i=0; i<n; i++) {
if(i) cout << " ";
cout << 1;
}
cout << "\n";
for(int i=1; i<n; i++) {
cout << i << " " << i+1 << "\n";
}
return;
}
const int INF = (int)1e9;
vector d(m, vector<int>(m, INF));
for(int i=0; i<m; i++)
for(int j=0; j<m; j++)
d[i][j] = g[rep[i]][rep[j]] - 1;
int r = 0;
vector<int> droot(m, INF);
int mx = 0;
for(int i=0; i<m; i++) {
droot[i] = d[r][i];
if(droot[i] < INF) mx = max(mx, droot[i]);
}
vector<vector<int>> buckets(mx+1);
for(int i=0; i<m; i++)
if(droot[i] < INF) buckets[droot[i]].push_back(i);
vector<vector<int>> nodes(mx+1);
vector<char> added(m, 0);
added[r] = 1;
nodes[0].push_back(r);
vector<pair<int, int>> edges;
for(int dd=1; dd<mx+1; dd++) {
for(int cur : buckets[dd]) {
int p = -1;
for(int cand : nodes[dd-1]) {
if(d[cand][cur] == 1) {
p = cand;
break;
}
}
if(p==-1) {
for(int pd=dd-1; ~pd && p==-1; --pd) {
for(int cand : nodes[pd]) {
if(d[cand][cur] == 1) {
p = cand;
break;
}
}
}
}
edges.emplace_back(p, cur);
added[cur] = 1;
nodes[dd].push_back(cur);
}
}
vector<pair<int, int>> fedges;
for(int i=0; i<m; i++) {
int rn = rep[i];
for(size_t k=1; k<ssize(comp[i]); ++k) {
fedges.emplace_back(rn+1, comp[i][k]+1);
}
}
for(auto &[u, v] : edges) {
fedges.emplace_back(u+1, v+1);
}
vector<int> c(n);
for(int i=0; i<m; i++) {
for(auto &j : comp[i])
c[j] = i+1;
}
for(int i=0; i<n; i++) {
if(i) cout << " ";
cout << c[i];
}
cout << "\n";
for(auto &[u, v] : fedges) {
cout << u << " " << v << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
