#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
using ll = long long;
const int maxn=1e3+5;
int p[maxn];
int nw[maxn];
vector<int>v[maxn];
int ata(int nd){
if(p[nd] == nd) return nd;
return p[nd] = ata(p[nd]);
}
int par(int nd){
if(nw[nd] == nd) return nd;
return nw[nd] = ata(nw[nd]);
}
int construct(vector<vector<int>> a) {
int n = a.size();
for(int i = 0;i < n;i++) p[i] = nw[i] = i;
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
if(a[i][j] == 3) return 0;
if(a[i][j] == 1){
int x = ata(i),y = ata(j);
if(x != y) p[y] = x;
}
}
}
for(int i = 0;i < n;i++) ata(i);
vector<vector<int>>ed;
ed.resize(n);
for(int i = 0;i < n;i++) ed[i].resize(n);
for(int i = 0;i < n;i++){
if(p[i] != i){
if(a[i] != a[p[i]]) return 0;
ed[p[i]][i] = 1;
ed[i][p[i]] = 1;
}
else {
for(int j = 0;j < n;j++){
if(p[j] != j or i == j) continue;
if(a[i][j] == 2){
int x = par(i),y = par(j);
if(x != y) nw[j] = i;
}
}
}
}
for(int i = 0;i < n;i++){
if(p[i] != i) continue;
par(i);
v[nw[i]].push_back(i);
}
for(int i = 0;i < n;i++){
if(p[i] != i) continue;
if(nw[i] != i) continue;
if((int)v[i].size() == 2) return 0;
for(int j = 0;j < (int)v[i].size();j++){
for(int k = 0;k < j;k++){
if(a[v[i][j]][v[i][k]] != 2) return 0;
}
if(j > 0){
ed[v[i][j]][v[i][j-1]]=1;
ed[v[i][j-1]][v[i][j]]=1;
}
}
if((int)v[i].size() > 1) ed[v[i].back()][v[i][0]]=1;
if((int)v[i].size() > 1) ed[v[i][0]][v[i].back()]=1;
}
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
if(i == j) continue;
if(p[i] == p[j] and a[i][j] != 1) return 0;
if(nw[i] == nw[j] and a[i][j] != 2) return 0;
if(p[i] != p[j] and nw[p[i]] != nw[p[j]] and a[i][j] != 0) return 0;
}
}
build(ed);
return 1;
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
2
1 0
0 1
*/
