#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
bool taken[1001];
int nums[1001], cycs[1001];
vector<vector<int>> paths;
vector<vector<int>> cycles;
vector<vector<int>> ans;
int construct(std::vector<std::vector<int>> p) {
vector<vector<int>>().swap(paths);
vector<vector<int>>().swap(cycles);
vector<vector<int>>().swap(ans);
int n = p.size();
ans.resize(n);
for(int i = 0; i < n; i++) {
ans[i].resize(n);
if(!taken[i]) {
taken[i] = true;
nums[i] = paths.size();
paths.push_back(vector<int>());
for(int j = i; j < n; j++) {
if(p[i][j] == 1) {
paths[nums[i]].push_back(j);
taken[j] = true;
nums[j] = nums[i];
}
}
}
}
// for(int i = 0; i < n; i++) cout << nums[i] << ' ';
// cout << '\n';
for(int i = 0; i < n; i++) taken[i] = false;
for(int i = 0; i < (int)paths.size(); i++) {
if(!taken[i]) {
taken[i] = true;
cycles.push_back(vector<int>());
cycles[cycles.size() - 1].push_back(i);
cycs[i] = cycles.size() - 1;
for(int j = i+1; j < (int)paths.size(); j++) {
if(p[paths[i][0]][paths[j][0]] == 2) {
taken[j] = true;
cycles[cycles.size() - 1].push_back(j);
cycs[j] = cycles.size() - 1;
}
}
}
}
// cout << "yehey\n";
// for(int i = 0; i < n; i++) cout << cycs[i] << ' ';
// cout << '\n';
bool sad = false;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
int pi = nums[i], pj = nums[j];
int ci = cycs[pi], cj = cycs[pj];
if(p[i][j] == 0) {
if(pi == pj || ci == cj) sad = true;
}
else if(p[i][j] == 1) {
if(pi != pj) sad = true;
}
else if(p[i][j] == 2) {
if(pi == pj || ci != cj) sad = true;
}
else {
sad = true;
}
}
}
if(sad) {
return 0;
}
// cout << "Yehey\n";
for(int i = 0; i < (int)paths.size(); i++) {
for(int j = 1; j < (int)paths[i].size(); j++) {
ans[paths[i][j]][paths[i][j-1]] = 1;
ans[paths[i][j-1]][paths[i][j]] = 1;
}
}
for(int i = 0; i < (int)cycles.size(); i++) {
if(cycles[i].size() == 1) continue;
ans[paths[cycles[i][0]][0]][paths[cycles[i][cycles[i].size() - 1]][0]] = 1;
ans[paths[cycles[i][cycles[i].size() - 1]][0]][paths[cycles[i][0]][0]] = 1;
for(int j = 1; j < (int)cycles[i].size(); j++) {
ans[paths[cycles[i][j-1]][0]][paths[cycles[i][j]][0]] = 1;
ans[paths[cycles[i][j]][0]][paths[cycles[i][j-1]][0]] = 1;
}
}
build(ans);
return 1;
}
