#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> par;
int fpar(int x) {
return x == par[x] ? x : par[x] =fpar(par[x]);
}
vector<vector<int>> splits(vector<vector<int>>&p, vector<int> scope, int mode) {
for(int i:scope) {
for(int j:scope) {
if(p[i][j] == mode) continue;
if(fpar(i) == fpar(j)) continue;
par[fpar(i)] = fpar(j);
}
}
vector<bool> vis(n, 0);
vector<vector<int>> toret;
for(int i:scope) {
for(int j:scope) {
if(fpar(i) == fpar(j) && p[i][j] == mode) return {};
if(fpar(i) != fpar(j) && p[i][j] != mode) return {};
}
}
for(int i:scope) {
if(vis[fpar(i)]) continue;
vis[fpar(i)] = 1;
toret.push_back({});
for(int j:scope) {
if(fpar(i) == fpar(j)) toret.back().push_back(j);
}
}
return toret;
}
int construct(vector<vector<int>> p) {
n = p.size();
vector<vector<int>> answer;
int cmx = 0;
vector<int> og(n);
iota(og.begin(), og.end(), 0);
for (int i = 0; i < n; i++) {
vector<int> row(n, 0);
answer.push_back(row);
cmx = max(cmx, *max_element(p[i].begin(), p[i].end()));
}
if(cmx >= 3) return 0;
par.resize(n);
iota(par.begin(), par.end(), 0);
auto r1 = splits(p, og, 0);
if(r1.empty()) return 0;
par.resize(n);
iota(par.begin(), par.end(), 0);
for(auto &e:r1) {
auto r2 = splits(p, e, 2);
if(r2.empty()) return 0;
for(int i=0;i<r2.size()-1;i++) {
//cout << e.front() << '\n';
cout << r2[i].front() << ' ' << r2[i+1].front() << '\n';
answer[r2[i].front()][r2[i+1].front()] = answer[r2[i+1].front()][r2[i].front()] = 1;
}
if(r2.size() > 1) answer[r2[0].front()][r2.back().front()] = answer[r2.back().front()][r2[0].front()] = 1;
for(auto &e:r2) {
for(int i=1;i<e.size();i++) {
answer[e[i]][e[i-1]] = answer[e[i-1]][e[i]] = 1;
}
}
}
build(answer);
return 1;
}
