#include<bits/stdc++.h>
#include "supertrees.h"
#include <vector>
using namespace std;
typedef vector<int> vi;
#define FORi(i,a,b) for(int i=((int)a);i<((int)b);i++)
#define FOR(i,n) FORi(i,0,n)
#define FOA(v,a) for(auto v : a)
int par[10000];
int lef[10000];
vector<vi> adj;
int fnd(int a){
if(par[a]==a) return a;
par[a] = fnd(par[a]);
return par[a];
}
void onion(int a, int b){
par[fnd(a)] = fnd(b);
}
vi vis;
void dfs(int x){
vis[x] = true;
FOA(v, adj[x]) if(!vis[v]) dfs(v);
}
int construct(vector<vector<int>> p) {
int n = p.size();
FOR(i,n) par[i] = i;
adj.assign(n, vi(n, 0));
int deg[n] = {};
FOR(i,n){
bool none = true;
FOR(j,n){
if(i==j) continue;
if(p[i][j]==2 && fnd(i)!=fnd(j) && none){
onion(i, j);
adj[i][j] = 1;
adj[j][i] = 1;
deg[i]++;
deg[j]++;
none = false;
}
else if(p[i][j]==0 && fnd(i)==fnd(j)){
return 0;
}
}
}
FOR(i,n){
if(deg[i]==1){
FOR(j,n) if(fnd(i)==fnd(j) && deg[j]==1 && i!=j){
deg[i]++;
deg[j]++;
adj[i][j] = 1;
adj[j][i] = 1;
}
}
}
FOR(i,n){
vis.assign(n, 0);
dfs(i);
FOR(j,n) if(vis[i] && !p[i][j]) return 0;
}
build(adj);
return 1;
}
