#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
vector< vector<int> > ans;
vector<int> p;
int root(int x) {
if (p[x] == -1) return x;
return p[x] = root(p[x]);
}
void connect(int x, int y, bool b = true) {
x = root(x); y = root(y);
if (x != y) {
p[y] = x;
if (b) ans[x][y] = ans[y][x] = 1;
}
}
int construct(vector< vector<int> > a) {
int n = a.size();
ans.assign(n, vector<int>(n, 0));
p.assign(n, -1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] >= 3) return 0;
if (a[i][j] == 1) connect(i, j);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (root(i) == root(j) && a[i][j] != 1) return 0;
}
}
vector<bool> is_root(n);
for (int i = 0; i < n; i++) is_root[i] = root(i) == i;
p.assign(n, -1);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (is_root[i] && is_root[j] && a[i][j] == 2) connect(i, j, false);
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (i != j && root(i) == root(j) && a[i][j] != 2) return 0;
for (int i = 0; i < n; i++) {
if (root(i) != i) continue;
vector<int> tmp;
for (int j = 0; j < n; j++) if (root(j) == i) tmp.push_back(j);
if ((int) tmp.size() == 1) continue;
if ((int) tmp.size() == 2) return 0;
for (int i = 1; i < (int) tmp.size(); i++) ans[tmp[i - 1]][tmp[i]] = ans[tmp[i]][tmp[i - 1]] = 1;
ans[tmp[0]][tmp.back()] = ans[tmp.back()][tmp[0]] = 1;
}
build(ans);
return 1;
}
