#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;
const int N = 1e3;
int dsu[3][N+2];
int find(int idx, int x) {
if (dsu[idx][x] == x)
return x;
return dsu[idx][x] = find(idx,dsu[idx][x]);
}
void merge(int idx, int a, int b) {
int ra = find(idx,a);
int rb = find(idx,b);
dsu[idx][ra] = rb;
}
bool connect(int idx, int a, int b) {
return (find(idx,a) == find(idx,b));
}
int construct(vector<vector<int>> p) {
int n = p.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j <= 2; j++) {
dsu[j][i] = i;
}
}
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
if (p[i][j] == 3)
return 0;
if (p[i][j] != 0)
merge(0,i,j);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 0 && connect(0,i,j))
return 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 1)
merge(1,i,j);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 2 && connect(1,i,j))
return 0;
}
}
vector<vector<int>> ans(n,vector<int>(n,0));
for (int i = 0; i < n; i++) {
int r = find(1,i);
if (r != i) {
ans[i][r] = 1;
ans[r][i] = 1;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int u = find(1,i);
int v = find(1,j);
if (p[u][v] == 2)
merge(2,u,v);
}
}
vector<vector<int>> ls(n);
for (int i = 0; i < n; i++) {
ls[find(2,i)].pb(i);
}
for (int i = 0; i < n; i++) {
int sz = ls[i].size();
if (sz <= 1)
continue;
if (sz == 2)
return 0;
for (int j = 0; j < sz; j++) {
int u = ls[i][(j+1)%sz];
int v = ls[i][j];
ans[u][v] = 1;
ans[v][u] = 1;
}
}
// Subsoal 3
// vector<vector<int>> ls(n);
// for (int i = 0; i < n; i++) {
// ls[find(i)].pb(i);
// }
// for (int i = 0; i < n; i++) {
// int sz = ls[i].size();
// if (sz <= 1)
// continue;
// if (sz == 2)
// return 0;
// for (int j = 0; j < sz; j++) {
// int u = ls[i][(j+1)%sz];
// int v = ls[i][j];
// ans[u][v] = 1;
// ans[v][u] = 1;
// }
// }
// Subsoal 1
// for (int i = 1; i < n; i++) {
// ans[i-1][i] = 1;
// ans[i][i-1] = 1;
// }
build(ans);
return 1;
}
