#include "supertrees.h"
#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define dbg(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
using ii = pair<int,int>;
const int N = 1003;
int n;
vector<vector<int>> adj;
struct disjoint_set {
int p[N];
disjoint_set(){ iota(p,p+N,0); }
int find(int x){
if (x==p[x]) return x;
return p[x]=find(p[x]);
}
bool same(int a, int b){ return find(a)==find(b); }
void merge(int a, int b) {
a = find(a), b = find(b);
assert(a!=b);
p[a]=b;
}
} ds, DS;
bool found3(vector<vector<int>> &p) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (p[i][j] == 3) return true;
}
}
return false;
}
vector<int> roots;
void connect_ones(vector<vector<int>> &p) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) if (p[ds.find(i)][ds.find(j)] == 1) {
if (not ds.same(i,j)) {
adj[ds.find(i)][ds.find(j)] =
adj[ds.find(j)][ds.find(i)] = 1;
ds.merge(i,j);
}
}
}
}
bool doit(vector<vector<int>> &p) {
for (int i = 0; i < n; ++i) roots.push_back(ds.find(i));
sort(all(roots)), roots.erase(unique(all(roots)),end(roots));
for (auto r1 : roots) for (auto r2 : roots) if (p[r1][r2] == 2) {
if (not DS.same(r1,r2)) DS.merge(r1,r2);
}
vector<vector<int>> comp(n);
for (auto r : roots) comp[DS.find(r)].push_back(r);
for (auto &c : comp) {
if (siz(c) < 2) continue;
if (siz(c) == 2) return false;
for (int j = 0; j < siz(c); ++j) {
adj[c[j]][c[(j+1)%siz(c)]] = 1;
adj[c[(j+1)%siz(c)]][c[j]] = 1;
}
}
return true;
}
int construct(vector<vector<int>> p) {
n = p.size(), adj.resize(n,vector<int>(n));
if (found3(p)) return 0;
connect_ones(p);
if (!doit(p)) return 0;
for (int i = 0; i < n; ++i) {
adj[i][i] = 0;
for (int j = 0; j < n; ++j) if (i != j) {
if (p[i][j] == 0) {
if (ds.same(i,j)) return 0;
if (DS.same(ds.find(i),ds.find(j))) return 0;
} else if (p[i][j] == 1) {
if (not ds.same(i,j)) return 0;
} else if (p[i][j] == 2) {
if (ds.same(i,j)) return 0;
if (not DS.same(ds.find(i),ds.find(j))) return 0;
} else assert(0);
}
}
build(adj);
return 1;
}
