#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ii pair<int, int>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define F0R(i, n) for (int i = 0; i < n; i++)
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define inf 1000000010
#define maxn 3000
int n;
int input[maxn][maxn];
vector<int> nodes; // stores nodes remaining after 1's are compressed
map<int, vector<int>> nodesInOneComponent;
void compressOnes() {
vector<bool> done(n, 0);
F0R(i, n) {
if (done[i]) continue;
nodes.pb(i);
done[i] = true;
F0R(j, n) {
if (input[i][j] == 1 && j != i) {
nodesInOneComponent[i].pb(j);
done[j] = true;
}
}
}
}
vector<vector<int>> twoComponents;
bool inSameComponent[maxn][maxn];
vector<int> components[maxn];
void findTwos() {
for (int n1 : nodes) {
for (int n2 : nodes) {
if (inSameComponent[n1][n2]) continue;
if (input[n1][n2] != 2) continue;
twoComponents.pb(vector<int>());
twoComponents.back().pb(n1);
twoComponents.back().pb(n2);
for (int n3 : nodes) {
if (input[n1][n3] == 2 && input[n2][n3] == 2) {
twoComponents.back().pb(n3);
}
}
for (int x : twoComponents.back()) {
for (int y : twoComponents.back()) {
inSameComponent[x][y] = 1;
}
components[x].pb(twoComponents.size()-1);
}
}
}
/*
for (auto x : twoComponents) {
for (auto y : x) {
cout << y << " ";
}
cout << endl;
}
cout << "---" << endl;
*/
}
int assignedColor[maxn];
vector<ii> outputEdges;
vector<int> adj[maxn];
bool inQueue[maxn];
map<int, int> colors;
int target = -1;
int findColor(int u, int p) {
if ((int)colors.size() == input[target][u]) {
return assignedColor[u];
}
for (int v : adj[u]) {
if (v == p) continue;
colors[assignedColor[v]]++;
int r = findColor(v, u);
colors[assignedColor[v]]--;
if (colors[assignedColor[v]] == 0) {
colors.erase(assignedColor[v]);
}
if (r != 0) return r;
}
return 0;
}
void buildTree() {
int colors = 2;
assignedColor[nodes[0]] = 1;
queue<int> q;
for (int c : components[nodes[0]]) {
q.push(c);
inQueue[c] = true;
}
while (!q.empty()) {
int c = q.front(); q.pop();
int rootNode = -1;
int childNode = -1;
for (int x : twoComponents[c]) {
if (assignedColor[x] > 0) {
assert(rootNode == -1);
rootNode = x;
} else {
childNode = x;
}
}
adj[childNode].pb(rootNode);
adj[rootNode].pb(childNode);
outputEdges.pb(mp(childNode, rootNode));
target = childNode;
assignedColor[childNode] = findColor(childNode, childNode);
if (assignedColor[childNode] == 0) {
assignedColor[childNode] = colors++;
}
for (int x : twoComponents[c]) {
if (x != rootNode && x != childNode) {
assignedColor[x] = assignedColor[childNode];
adj[x].pb(rootNode);
adj[rootNode].pb(x);
outputEdges.pb(mp(x, rootNode));
}
for (int c : components[x]) {
if (!inQueue[c]) {
q.push(c);
inQueue[c] = true;
}
}
}
}
}
void decompressOnes() {
for (int x : nodes) {
for (int y : nodesInOneComponent[x]) {
outputEdges.pb(mp(x, y));
assignedColor[y] = assignedColor[x];
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int subtask; cin >> subtask;
cin >> n;
F0R(i, n) {
F0R(j, n) {
cin >> input[i][j];
}
}
compressOnes();
findTwos();
buildTree();
decompressOnes();
F0R(i, n) cout << assignedColor[i] << " ";
cout << endl;
for (auto x : outputEdges) cout << x.f+1 << " " << x.s+1 << endl;
assert((int)outputEdges.size()==n-1);
F0R(i, n) assert(assignedColor[i]>0);
return 0;
}
