#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int N = 1000;
int nn;
bool vst[N], mark[N];
vector<vector<int>> a;
void Dfs(int u, int val, vector<int> &vexs) {
if (vst[u])
return;
vst[u] = 1;
vexs.push_back(u);
for(int v = 0; v < nn; v++)
if (a[u][v] == val)
Dfs(v, val, vexs);
}
int construct(vector<vector<int>> p) {
a = p;
nn = a.size();
int maxA = 0;
for(int i = 0; i < nn; i++)
for(int j = 0; j < nn; j++)
maxA = max(maxA, a[i][j]);
if (maxA == 3)
return 0;
vector<vector<int>> res(nn, vector<int>(nn, 0));
memset(vst, 0, sizeof(vst));
memset(mark, 0, sizeof(mark));
for(int i = 0; i < nn; i++)
for(int j = 0; j < nn; j++)
if (a[i][j] == 2)
mark[i] = 1;
for(int i = 0; i < nn; i++)
vst[i] = mark[i] ^ 1;
for(int u = 0; u < nn; u++) {
if (vst[u])
continue;
vector<int> vexs;
Dfs(u, 1, vexs);
for(int i = 0; i < (int) vexs.size(); i++)
for(int j = i + 1; j < (int) vexs.size(); j++)
if (a[vexs[i]][vexs[j]] != 1)
return 0;
for(int i = 1; i < (int) vexs.size(); i++)
res[vexs[i - 1]][vexs[i]] = res[vexs[i]][vexs[i - 1]] = 1;
}
build(res);
return 1;
}
