/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
typedef long long ll;
const int N_MAX = 1002;
void build (vector <vector <int> > answer);
int n;
vector <int> edges[N_MAX];
bool visited[N_MAX];
vector <int> aux;
void dfs (int u)
{
visited[u] = true;
aux.push_back(u);
for(int v : edges[u])
if(visited[v] == false)
dfs(v);
}
bool chainRoot[N_MAX];
int chainIndex[N_MAX];
int cycleIndex[N_MAX];
int root[N_MAX];
int construct (vector <vector <int> > p)
{
n = p.size();
vector <vector <int> > answer;
answer.resize(n);
for(int i = 0; i < n; i++)
answer[i].resize(n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
answer[i][j] = false;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(p[i][j] == 3)
return false;
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(p[i][j] == 1)
edges[i].push_back(j);
int curr;
curr = 0;
for(int i = 0; i < n; i++)
if(visited[i] == false)
{
dfs(i);
chainRoot[i] = true;
curr++;
for(int j = 0; j < (int)aux.size(); j++)
chainIndex[aux[j]] = curr;
root[curr] = i;
for(int j = 1; j < (int)aux.size(); j++)
answer[aux[j - 1]][aux[j]] = answer[aux[j]][aux[j - 1]] = true;
aux.clear();
}
for(int i = 0; i < n; i++)
{
edges[i].clear();
visited[i] = false;
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(p[i][j] == 2)
edges[i].push_back(j);
for(int i = 0; i < n; i++)
if(chainRoot[i] == false)
visited[i] = true;
curr = 0;
for(int i = 0; i < n; i++)
if(visited[i] == false)
{
dfs(i);
chainRoot[i] = true;
curr++;
if((int)aux.size() == 2)
return false;
for(int j = 0; j < (int)aux.size(); j++)
cycleIndex[aux[j]] = curr;
for(int j = 0; j < (int)aux.size(); j++)
{
int j1 = j - 1;
if(j == 0)
j1 += (int)aux.size();
if(j != j1)
answer[aux[j1]][aux[j]] = answer[aux[j]][aux[j1]] = true;
}
aux.clear();
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(i != j)
{
int cnt = 0;
if(cycleIndex[root[chainIndex[i]]] == cycleIndex[root[chainIndex[j]]] && chainIndex[i] != chainIndex[j])
cnt = 2;
else if(chainIndex[i] == chainIndex[j])
cnt = 1;
else
cnt = 0;
if(cnt != p[i][j])
return false;
}
build(answer);
return true;
}
