#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
//
const int mxN = 1001;
vector<vector<int>> paths;
int n;
bool vis[mxN];
void resetvis() {
for (int i = 0; i < n; i++) vis[i] = false;
}
vector<vector<int>> components;
vector<int> curcomponent;
void dfs(int u, int tar) {
curcomponent.pb(u);
vis[u] = true;
for (int v = 0; v < n; v++) {
if (u != v && 1 <= paths[u][v] && paths[u][v] <= tar && !vis[v]) {
dfs(v, tar);
}
}
}
int rep[mxN];
int repcnt = 1;
bool fullsol() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (paths[i][j] == 3) return false;
}
}
for (int i = 0; i < n; i++) {
if (!vis[i]) {
dfs(i, 2);
for (int &x : curcomponent) rep[x] = repcnt;
repcnt++;
components.pb(curcomponent);
curcomponent.clear();
}
}
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
if (rep[u] == rep[v] && paths[u][v] == 0) return false;
if (rep[u] != rep[v] && paths[u][v] != 0) return false;
}
}
for (int i = 0; i < n; i++) rep[i] = 0;
repcnt = 1;
resetvis();
vector<vector<int>> ans(n);
for (int i = 0; i < n; i++) ans[i].resize(n, 0);
vector<vector<int>> decomp;
for (vector<int> &cur : components) {
decomp.clear();
for (int &u : cur) {
for (int &v : cur) {
if (!vis[u] && paths[u][v] == 1) {
dfs(u, 1);
for (int &x : curcomponent) rep[x] = repcnt;
repcnt++;
decomp.pb(curcomponent);
curcomponent.clear();
break;
}
}
if (!vis[u]) decomp.pb({u});
}
// cerr << "debug rep: ";
// for (int i = 0; i < n; i++) cerr << rep[i] << ' ';
// cerr << endl;
for (int &u : cur) {
for (int &v : cur) {
if (paths[u][v] != 1 + (rep[u] != rep[v])) return false;
}
}
for (vector<int> &process : decomp) {
if (process.size() >= 2) {
for (int i = 1; i < int(process.size()); i++) {
ans[process[i - 1]][process[i]] = 1;
}
}
}
if (decomp.size() >= 2) {
for (int i = 1; i < int(decomp.size()); i++) {
ans[decomp[i - 1][0]][decomp[i][0]] = 1;
}
ans[decomp.front()[0]][decomp.back()[0]] = 1;
}
}
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
ans[u][v] |= ans[v][u];
ans[v][u] |= ans[u][v];
}
}
build(ans);
return true;
}
int construct(vector<vector<int>> p) {
n = p.size(); paths = p;
return fullsol();
}
