#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
int v[1002],p,n,cnt,s,k[1002],ind[1002];
vector<vector<int>> mar,rasp;
vector<int> q;
void atr(int a,int b) {
rasp[a][b]=rasp[b][a]=1;
}
void dfs(int nod){
int i;
q.push_back(nod);
k[nod]=nod;v[nod]=1;ind[nod]=cnt;
for(i=0;i<n;i++){
if(!v[i] && mar[nod][i]==1){
v[i]=1;k[i]=nod;ind[i]=cnt;atr(nod,i);
}
}
for(i=0;i<n;i++){
if(!v[i] && mar[nod][i]==2) dfs(i);
}
}
int construct(vector<vector<int>> x){
int i,j;
n=x.size();mar=x;
rasp.resize(n);
for(i=0;i<n;i++){
for(j=0;j<n;j++)
rasp[i].push_back(0);
}
for (i=0;i<n;i++) {
if(!v[i]){
dfs(i);cnt++;
}
s=q.size();
if(s>1) {
if(s==2) p=1;
for(i=1;i<s;i++)
atr(q[i-1],q[i]);
atr(q[0],q[s-1]);
}
q.clear();
}
for(i=0;i<n;i++){
for(j=0;j<n;j++) {
if(k[i]==k[j] && mar[i][j]!=1) p=1;
if(ind[i]==ind[j] && k[i]!=k[j] && mar[i][j]!=2) p=1;
if(ind[i]!=ind[j]&& mar[i][j]) p=1;
}
}
if(p) return 0;
else build(rasp);
return 1;
}
