#include "supertrees.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
static const int N = 1010;
static vector<int> one[N];
static vector<int> two[N];
static bool vis[N];
static int col[N];
static vector<vector<int>> B;
int construct(std::vector<std::vector<int>> p) {
int n = p.size();
B = vector<vector<int>>(n, vector<int>(n, 0));
Loop (i,0,n) Loop (j,0,n) {
if (p[i][j] == 3)
return 0;
}
int n1 = 0;
Loop (i,0,n) {
if (vis[i])
continue;
Loop (j,0,n)
if (p[i][j] == 1) {
one[n1].push_back(j);
vis[j] = 1;
col[j] = n1;
if (i != j)
B[i][j] = B[j][i] = 1;
}
for (int x : one[n1])
for (int y : one[n1])
if (p[x][y] != 1)
return 0;
++n1;
}
Loop (i,0,n1)
Loop (j,i+1,n1)
for (int x : one[i])
for (int y : one[j])
if (p[x][y] == 1)
return 0;
memset(vis, 0, sizeof(vis));
int n2 = 0;
Loop (i,0,n) {
if (vis[col[i]])
continue;
vis[col[i]] = 1;
two[n2].push_back(col[i]);
Loop (j,0,n)
if (p[i][j] == 2) {
two[n2].push_back(col[j]);
vis[col[j]] = 1;
}
if (two[n2].size() == 1) {
n2++;
continue;
}
for (int x : two[n2])
for (int y : two[n2])
if (x != y)
for (int a : one[x])
for (int b : one[y])
if (p[a][b] != 2)
return 0;
if (two[n2].size() == 2) {
if (one[two[n2][0]].size() >= 2) {
B[one[two[n2][0]][0]][one[two[n2][1]][0]] = 1;
B[one[two[n2][1]][0]][one[two[n2][0]][0]] = 1;
B[one[two[n2][0]][1]][one[two[n2][1]][0]] = 1;
B[one[two[n2][1]][0]][one[two[n2][0]][1]] = 1;
} else if (one[two[n2][1]].size() >= 2) {
B[one[two[n2][0]][0]][one[two[n2][1]][0]] = 1;
B[one[two[n2][1]][0]][one[two[n2][0]][0]] = 1;
B[one[two[n2][0]][0]][one[two[n2][1]][1]] = 1;
B[one[two[n2][1]][1]][one[two[n2][0]][0]] = 1;
} else {
return 0;
}
}
if (two[n2].size() >= 3) {
Loop (i,0,two[n2].size()) {
int j = (i+1) % two[n2].size();
B[one[two[n2][i]][0]][one[two[n2][j]][0]] = 1;
B[one[two[n2][j]][0]][one[two[n2][i]][0]] = 1;
}
}
n2++;
}
Loop (i,0,n2)
Loop (j,i+1,n2)
for (int x : two[i])
for (int y : two[j])
for (int a : one[x])
for (int b : one[y])
if (p[a][b])
return 0;
build(B);
return 1;
}
