#include "supertrees.h"
#include <vector>
#include <iostream>
using namespace std;
const int mxN = 1000;
vector<int> boss1(mxN), boss2(mxN), under1(mxN, 1), under2(mxN, 1);
int find1(int i) {
if (boss1[i] == i) return i;
return boss1[i] = find1(boss1[i]);
}
int find2(int i) {
if (boss2[i] == i) return i;
return boss2[i] = find2(boss2[i]);
}
void unite1(int i, int j) {
i = find1(i);
j = find1(j);
if (i == j) return;
if (under1[i] > under1[j]) swap(i, j);
under1[j] += under1[i];
boss1[i] = j;
}
void unite2(int i, int j) {
i = find2(i);
j = find2(j);
if (i == j) return;
if (under2[i] > under2[j]) swap(i, j);
under2[j] += under2[i];
boss2[i] = j;
}
int construct(vector<vector<int>> p) {
int n = p.size();
for (int i = 0; i < n; ++i) boss1[i] = boss2[i] = i;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j && p[i][j]!=1) return 0;
if (p[i][j] == 1) unite1(i, j);
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (p[i][j] == 2) unite2(find1(i), find1(j));
}
}
for (int _i = 0; _i < n; ++_i) {
for (int _j = 0; _j < n; ++_j) {
if (_i == _j) continue;
int i = find1(_i), j = find1(_j);
if (p[i][j] == 3) { cerr << "3!\n"; return 0; };
if ((p[i][j]==0 || p[i][j]==2) && i==j) { cerr << "same tree\n"; return 0; }
if (p[i][j]==0 && find2(i) == find2(j)) { cerr << "same cycle\n"; return 0; }
}
}
vector<vector<int>> ans(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
if (find1(i) != i) ans[i][boss1[i]] = ans[boss1[i]][i] = 1;
}
vector<int> cycles[n];
for (int i = 0; i < n; ++i) {
if (boss1[i] == i) {
cycles[find2(i)].push_back(i);
}
}
for (int i = 0; i < n; ++i) {
if (cycles[i].size() == 2) return 0;
if (cycles[i].size() <= 1) continue;
for (int j = 0; j < (int)cycles[i].size(); ++j) {
ans[cycles[i][(j+1)%cycles[i].size()]][cycles[i][j]] =
ans[cycles[i][j]][cycles[i][(j+1)%cycles[i].size()]] = 1;
}
}
build(ans);
return 1;
}
