#include "supertrees.h"
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
vector<vector<int>> ans;
int n;
vector<int> graf1[1000];
bitset<1000> odw;
vector<vector<int>> p;
int tree[1000];
int pop_tree[1000];
int rep_t[1000];
int rep[1000];
int typ_pol[1000];
vector<int> cycle[1000];
vector<int> v_on_tree[1000];
int akttree = 0;
int find_(int v)
{
if(rep[v] == v) return v;
rep[v] = find_(rep[v]); return rep[v];
}
int union_(int a, int b, int a2, int b2)
{
rep[find_(b)] = find_(a);
if(typ_pol[find_(b)] == -1 || typ_pol[find_(a)] == -1)
{
typ_pol[find_(b)] = max(typ_pol[find_(b)],typ_pol[find_(a)]);
typ_pol[find_(a)] = max(typ_pol[find_(b)],typ_pol[find_(a)]);
}
if(typ_pol[find_(b)] == -1)
{
typ_pol[find_(b)] = p[a2][b2];
typ_pol[find_(a)] = p[a2][b2];
}
//cout << typ_pol[find_(a)] << " " << typ_pol[find_(b)] << " " << a2 << " " << b2 << " typy\n";
if(typ_pol[find_(a)] != typ_pol[find_(b)] || p[a2][b2] != typ_pol[find_(a)])
{
return -1;
}
return 0;
}
void dfs(int v)
{
odw[v] = 1;
tree[v] = akttree;
v_on_tree[akttree].push_back(v);
rep_t[akttree] = v;
for(auto& it: graf1[v]) if(odw[it] == 0) dfs(it);
}
int construct(vector<vector<int>> p2) {
p = p2;
n = (int)p.size();
ans.resize(n);
rep(i,n)
{
typ_pol[i] = -1;
pop_tree[i] = -1;
rep(j,n)
ans[i].push_back(0);
rep[i] = i;
}
rep(i,n) rep(j,n)
{
if(p[i][j] == 3) return 0;
if(p[i][j] == 1 && i != j) graf1[i].push_back(j);
}
rep(i,n)
{
if(odw[i] == 0)
{
dfs(i);
akttree++;
}
}
rep(i,n) rep(j,n)
{
if(tree[i] == tree[j] && p[i][j] != 1)
{
//cout << " zle tree\n";
return 0;
}
}
rep(i,n) rep(j,n)
{
if(p[i][j] >= 2 && tree[i] != tree[j])
{
// cout << i << " " << j << " " << tree[i] << " " << tree[j] << " union\n";
if(union_(tree[i],tree[j],i,j) == -1)
{
//cout << tree[i] << " " << tree[j] << " " << i << " " << j << " zle union\n";
return 0;
}
}
}
rep(i,n)
{
if(pop_tree[tree[i]] != -1)
{
ans[i][pop_tree[tree[i]]] = 1;
ans[pop_tree[tree[i]]][i] = 1;
}
pop_tree[tree[i]] = i;
}
rep(i,akttree)
{
rep(j,akttree)
{
if(find_(i) == find_(j) && i < j)
{
for(auto& it1: v_on_tree[i])
{
for(auto& it2: v_on_tree[j])
{
if(p[it1][it2] == 0 || p[it1][it2] == 1) return 0;
}
}
}
}
}
rep(i,akttree)
{
//cout << find_(i) << " " << rep_t[i]<< " find\n";
cycle[find_(i)].push_back(rep_t[i]);
}
rep(i,n)
{
int ile = (int)cycle[i].size();
if(ile == 0) continue;
if(ile == 1) continue;
//cout << ile << " " << i << " cycle\n";
int typ = p[cycle[i][0]][cycle[i][1]];
if(typ == 0)
{
//cout << " typ 0\n";
return 0;
}
if(typ == 2)
{
if(ile < 3)
{
//cout << " ile < 3\n";
return 0;
}
for(int j = 0; j < ile-1; j++)
{
ans[cycle[i][j]][cycle[i][j+1]] = 1;
ans[cycle[i][j+1]][cycle[i][j]] = 1;
}
ans[cycle[i][0]][cycle[i][ile-1]] = 1;
ans[cycle[i][ile-1]][cycle[i][0]] = 1;
}
}
build(ans);
return 1;
}
