#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int link[1005], sz[1005], link2[1005], sz2[1005];
vector<int> vec[1005], vec2[1005];
int find(int x) {
if (x == link[x]) return x;
return link[x] = find(link[x]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return;
if (sz[b] > sz[a]) swap(a, b);
sz[a] += sz[b];
for (int i : vec[b]) vec[a].pb(i);
link[b] = a;
}
int find2(int x) {
if (x == link2[x]) return x;
return link2[x] = find2(link2[x]);
}
void unite2(int a, int b) {
a = find2(a);
b = find2(b);
if (a == b) return;
if (sz2[b] > sz2[a]) swap(a, b);
sz2[a] += sz2[b];
for (int i : vec2[b]) vec2[a].pb(i);
link2[b] = link2[a];
}
int construct(vector<vector<int> > p) {
int n = p.size();
vector<vector<int> > b(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) {
link[i] = i;
sz[i] = 1;
link2[i] = i;
sz2[i] = 1;
vec[i].pb(i);
vec2[i].pb(i);
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (p[i][j] == 1) unite(i, j);
else if (p[i][j] == 3) return 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (p[i][j] == 2) unite2(find(i), find(j));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (p[i][j] == 0 && find2(find(i)) == find2(find(j))) return 0;
else if (p[i][j] == 1 && find(i) != find(j)) return 0;
else if (p[i][j] == 2 && (find2(find(i)) != find2(find(j)) || find(i) == find(j))) return 0;
for (int i = 0; i < n; i++)
if (i == find(i) && i == find2(i)) {
if (vec2[i].size() == 2) return 0;
else if (vec2[i].size() == 1) {
for (int j = 0; j < (int)vec[i].size() - 1; j++)
b[vec[i][j]][vec[i][j + 1]] = b[vec[i][j + 1]][vec[i][j]] = 1;
} else {
for (int j : vec2[i])
for (int k = 0; k < (int)vec[j].size() - 1; k++)
b[vec[j][k]][vec[j][k + 1]] = b[vec[j][k + 1]][vec[j][k]] = 1;
for (int j = 0; j < (int)vec2[i].size() - 1; j++)
b[vec2[i][j]][vec2[i][j + 1]] = b[vec2[i][j + 1]][vec2[i][j]] = 1;
b[vec2[i][0]][vec2[i].back()] = b[vec2[i].back()][vec2[i][0]] = 1;
}
}
build(b);
return 1;
}
