#include "supertrees.h"//
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000 + 23;
vector<int> v[MAXN], v2[MAXN];
set<int> r, r2;
int n, num1[MAXN], num2[MAXN];// par[MAXN],
bitset<MAXN> b2[MAXN];
int construct(vector<vector<int>> p) {
n = p.size();
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (p[i][j] == 3) return 0;
for (int i = 0; i < n; i++) r.insert(i), v[i].push_back(i);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (p[i][j] == 1) num1[i]++;
for (int i = 0; i < n; i++) if (r.find(i) != r.end()) for (int j = i + 1; j < n; j++) if (r.find(j) != r.end()) if (p[i][j] == 1) {
while (v[j].size()) {
// par[v[j].back()] = i;
v[i].push_back(v[j].back());
v[j].pop_back();
}
r.erase(j);
}
vector<vector<int>> ans;
for (int i = 0; i < n; i++) {
vector<int> row;
row.resize(n);
ans.push_back(row);
}
for (auto i : r) r2.insert(i), v2[i].push_back(i);
for (auto i : r) {
for (auto j : v[i]) for (auto k : v[i]) if (p[k][j] != 1) return 0;
for (auto j : v[i]) if (num1[j] != (int)v[i].size()) return 0;
for (int j = 1; j < (int)v[i].size(); j++) ans[v[i][j - 1]][v[i][j]] = ans[v[i][j]][v[i][j - 1]] = 1;
}
for (auto i : r) for (auto j : r) if (i < j) {
int tmp = 0;
for (auto a : v[i]) for (auto b : v[j]) tmp |= (1 << p[a][b]);
if (tmp == 5) return 0;
if (tmp == 4) {
b2[i][j] = b2[j][i] = true;
num2[i]++;
num2[j]++;
}
}//upper is checked
for (auto i : r) if (r2.find(i) != r2.end()) for (auto j : r) if (i < j && r2.find(j) != r2.end()) if (b2[i][j]) {
while (v2[j].size()) {
v2[i].push_back(v2[j].back());
v2[j].pop_back();
}
r2.erase(j);
}
for (auto i : r2) {
if (v2[i].size() < 2) continue;
for (auto j : v2[i]) for (auto k : v2[i]) if (j != k && !b2[k][j]) return 0;
for (auto j : v2[i]) if (num2[j] != (int)v2[i].size() - 1) return 0;
if (v2[i].size() == 2) return 0;
for (int j = 1; j < (int)v2[i].size(); j++) ans[v2[i][j - 1]][v2[i][j]] = ans[v2[i][j]][v2[i][j - 1]] = 1;
ans[v2[i][v2[i].size() - 1]][v2[i][0]] = ans[v2[i][0]][v2[i][v2[i].size() - 1]] = 1;
}
// for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (ans[i][j] == true) cout << i << ' ' << j << endl;//
build(ans);//
return 1;
}
//int main() {cout << construct({{1, 2, 2, 0, 0, 0}, {2, 1, 2, 0, 0, 0}, {2, 2, 1, 0, 0, 0}, {0, 0, 0, 1, 2, 2}, {0, 0, 0, 2, 1, 2}, {0, 0, 0, 2, 2, 1}});}//
