#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> ans;
vector<vector<int>> p;
int n;
bool solve(vector<int> v)
{
int col[n]={}, cc=1;
vector<int> cyc;
for (int i:v)
{
if (col[i]) continue;
for (int j:v)
if (p[i][j]==1)
col[j]=cc;
cyc.push_back(i);
cc++;
}
for (int i:v)
for (int j:v)
if ((col[i]==col[j])!=(p[i][j]==1))
return 0;
if (cc==3) return 0;
for (int i=0;i<cyc.size();i++)
{
int u=cyc[i];
for (int j:v)
if (col[u]==col[j] && j!=u)
ans[u][j]=ans[j][u]=1;
if (i+1<cyc.size())
ans[u][cyc[i+1]]=ans[cyc[i+1]][u]=1;
else if(i)
ans[u][cyc[0]]=ans[cyc[0]][u]=1;
}
return 1;
}
int construct(vector<vector<int>> P)
{
p=P, n=p.size();
bool vis[n]={};
vector<vector<int>> cc;
ans=vector<vector<int>>(n,vector<int>(n));
for (int i=0;i<n;i++)
{
if (vis[i]) continue;
vector<int> v;
for (int j=0;j<n;j++)
if (p[i][j])
v.push_back(j), vis[j]=1;
cc.push_back(v);
}
for (int i=0;i<cc.size();i++)
for (int j=0;j<cc.size();j++)
{
for (int x:cc[i])
for (int y:cc[j])
if ((i==j)!=(p[x][y]>0) or p[x][y]==3)
return 0;
}
for (auto v:cc)
if (!solve(v))
return 0;
build(ans);
return 1;
}
