#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define F first
#define S second
vi p1(1001), p2(1001), sz1(1001, 1), sz2(1001, 1);
int get1(int a){
if (p1[a] == a) return a;
p1[a] = get1(p1[a]);
return p1[a];
}
void Union1(int a, int b){
int c = get1(a); int d = get1(b);
if (c == d) return;
if (sz1[c] >= sz1[d]){
p1[d] = c;
sz1[c] += sz1[d];
}else{
p1[c] = d;
sz1[d] += sz1[c];
}
}
int get2(int a){
if (p2[a] == a) return a;
p2[a] = get2(p2[a]);
return p2[a];
}
void Union2(int a, int b){
int c = get2(a); int d = get2(b);
if (c == d) return;
if (sz2[c] >= sz2[d]){
p2[d] = c;
sz2[c] += sz2[d];
}else{
p2[c] = d;
sz2[d] += sz2[c];
}
}
int construct(vector<vi> p) {
int n = p.size();
FOR(i, 0, n){
FOR(j, 0, n){
if (p[i][j] == 3) return 0;
}
}
FOR(i, 0, n){
p1[i] = i;
p2[i] = i;
}
FOR(i, 0, n){
FOR(j, 0, n){
if (p[i][j] == 1) Union1(i, j);
}
}
FOR(i, 0, n){
FOR(j, 0, n){
if (i == get1(i) && j == get1(j)){
if (p[i][j] == 2) Union2(i, j);
}
}
}
FOR(i, 0, n){
if (sz2[i] == 2) return 0;
}
vector<vi> ans;
FOR(i, 0, n){
vi row(n);
ans.pb(row);
}
FOR(i, 0, n){
FOR(j, 0, n){
if (p[i][j] == 0){
if (get2(get1(i)) == get2(get1(j))) return 0;
}
if (p[i][j] == 2){
if (get1(i) == get1(j) || get2(get1(i)) != get2(get1(j))) return 0;
}
}
}
vi g[n];
FOR(i, 0, n){
ans[get1(i)][i] = 1;
ans[i][get1(i)] = 1;
if (i == get1(i)){
g[get2(i)].pb(i);
}
}
FOR(i, 0, n){
if (get1(i) == i && get2(i) == i){
FOR(j, 0, sz2[i]){
ans[g[i][j]][g[i][(j+1)%sz2[i]]] = 1;
ans[g[i][(j+1)%sz2[i]]][g[i][j]] = 1;
}
}
}
FOR(i, 0, n){
ans[i][i] = 0;
}
build(ans);
return 1;
}
