#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1000;
struct DSU {
int dsu[mxN];
DSU () {iota(dsu, end(dsu), 0);}
int f(int x) {return dsu[x] == x ? x : dsu[x] = f(dsu[x]);}
void merge(int a, int b) {
a = f(a), b = f(b);
if (a!=b) dsu[a] = b;
}
} ldsu, cdsu;
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
std::vector<std::vector<int>> answer(n, vector<int>(n));
for (int i = 0; i < n; i++) for (int j = 0; j < n; ++j) {
if (p[i][j] == 3) return 0;
if (p[i][j]) {
cdsu.merge(i,j);
}
if (p[i][j] == 1) {
ldsu.merge(i,j);
}
}
for (int i = 0; i < n; i++) for (int j = 0; j < n; ++j) {
if (p[i][j] == 0 && cdsu.f(i) == cdsu.f(j)) {
return 0;
}
if (p[i][j] == 2 && ldsu.f(i) == ldsu.f(j)) {
return 0;
}
}
vector<vector<int>> ls(n), cs(n);
for (int i = 0; i < n; ++i) {
int l = ldsu.f(i);
if (ls[l].size()) answer[ls[l].back()][i] = answer[i][ls[l].back()] = 1;
ls[l].push_back(i);
}
for (int j = 0; j < n; ++j) if (ls[j].size()) {
int i = ls[j].back();
int c = cdsu.f(i);
if (cs[c].size()) answer[cs[c].back()][i] = answer[i][cs[c].back()] = 1;
cs[c].push_back(i);
}
for (int i = 0; i < n; ++i) if (cs[i].size()) {
if (cs[i].size() == 2) return 0;
if (cs[i].size() > 2) {
answer[cs[i].back()][cs[i].front()] = answer[cs[i].front()][cs[i].back()] = 1;
}
}
build(answer);
return 1;
}
