//Challenge: Accepted
#include "supertrees.h"
#include <vector>
#include <iostream>
#define maxn 1005
using namespace std;
int par[maxn];
vector<int> group[maxn];
int getpar(int a) {
return a == par[a] ? a : par[a] = getpar(par[a]);
}
void combine(int a, int b) {
par[getpar(a)] = getpar(b);
}
int construct(vector<vector<int> > p) {
int n = p.size();
int type = 1;
for (int i = 0;i < n;i++) par[i] = i;
for (int i = 0;i < n;i++) {
for (int j = i + 1;j < n;j++) {
if (p[i][j]) {
type = p[i][j];
combine(i, j);
}
}
}
for (int i = 0;i < n;i++) {
par[i] = getpar(i);
group[par[i]].push_back(i);
}
vector<vector<int> > ans;
for (int i = 0;i < n;i++) {
vector<int> add(n, 0);
ans.push_back(add);
}
for (int i = 0;i < n;i++) {
int x = group[i].size();
for (int j = 0;j < x;j++) {
for (int k = j + 1;k < x;k++) {
if (p[group[i][j]][group[i][k]] == 0) {
return 0;
}
}
if (j) {
ans[group[i][j - 1]][group[i][j]] = ans[group[i][j]][group[i][j - 1]] = 1;
}
if (type == 2) {
ans[group[i][0]][group[i][x - 1]] = ans[group[i][x - 1]][group[i][0]] = 1;
if (x == 2){
return 0;
}
}
}
}
/*
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
cout << ans[i][j] << " ";
}
cout << endl;
}
*/
build(ans);
return 1;
}
