#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int c=1002;
bool v[c], p;
int n, cnt, ki[c], id[c], si;
vector<vector<int> >sz, sol;
vector<int> kor;
void el(int a, int b) {
sol[a][b]=1, sol[b][a]=1;
}
void dfs(int a) {
kor.push_back(a);
ki[a]=a, v[a]=1, id[a]=cnt;
for (int i=0; i<n; i++) if (!v[i] && sz[a][i]==1) v[i]=1, ki[i]=a, id[i]=cnt, el(a, i);
for (int i=0; i<n; i++) if (!v[i] && sz[a][i]==2) dfs(i);
}
int construct(vector<vector<int> > x) {
n=x.size(), sz=x;
sol.resize(n);
for (int i=0; i<n; i++) for (int j=0; j<n; j++) sol[i].push_back(0);
for (int i=0; i<n; i++) {
if (!v[i]) dfs(i), cnt++;
si=kor.size();
if (si>1) {
if (si==2) p=1;
for (int i=1; i<si; i++) el(kor[i-1], kor[i]);
el(kor[0], kor[si-1]);
}
kor.clear();
}
for (int i=0; i<n; i++) for (int j=0; j<n; j++) {
if (ki[i]==ki[j] && sz[i][j]!=1) p=1;
if (id[i]==id[j] && ki[i]!=ki[j] && sz[i][j]!=2) p=1;
if (id[i]!=id[j]&& sz[i][j]) p=1;
}
if (p) return 0;
else build(sol);
return 1;
}
