#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
const int N = 1005;
bool used[N];
vector<vector<int> > b;
int comp[N], line[N];
int construct(vector<vector<int> > p) {
int n = p.size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(p[i][j] == 3) {
return 0;
}
}
vector<int> v;
v.resize(n);
b.push_back(v);
}
//cout<<"Came!"<<endl;
for(int i = 0; i < n; i++) {
if(used[i]) {
continue;
}
//cout<<"I: "<<i<<endl;
vector<int> cycle;
deque<int> D;
D.push_back(i);
while(D.size()) {
int x = D.front();
D.pop_front();
if(used[x]) {
continue;
}
//cout<<"X: "<<x<<endl;
vector<int> curr;
deque<int> G;
G.push_back(x);
cycle.push_back(x);
while(G.size()) {
int y = G.front();
G.pop_front();
if(used[y]) {
continue;
}
//cout<<"Y: "<<y<<endl;
used[y] = true;
comp[y] = i;
line[y] = x;
curr.push_back(y);
for(int j = 0; j < n; j++) {
if(p[y][j] == 1) {
G.push_back(j);
} else if(p[y][j] == 2) {
D.push_back(j);
}
}
}
if(curr.size() > 1) {
for(int j = 0; j < (int)curr.size() - 1; j++) {
b[curr[j]][curr[j + 1]] = 1;
b[curr[j + 1]][curr[j]] = 1;
}
}
}
if(cycle.size() == 2) {
return 0;
}
if(cycle.size() == 1) {
continue;
}
for(int j = 0; j < (int)cycle.size(); j++) {
b[cycle[j]][cycle[j + 1]] = 1;
b[cycle[j + 1]][cycle[j]] = 1;
}
b[cycle[0]][cycle[(int)cycle.size() - 1]] = 1;
b[cycle[(int)cycle.size() - 1]][cycle[0]] = 1;
}
/*cout<<"Came!"<<endl;
cout<<"Lines: "<<endl;
for(int i = 0; i < n; i++) {
cout<<line[i]<<" ";
}
cout<<endl;
cout<<"Comps: "<<endl;
for(int i = 0; i < n; i++) {
cout<<comp[i]<<" ";
}
cout<<endl;*/
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(line[i] == line[j]) {
if(p[i][j] != 1) {
return 0;
}
} else if(comp[i] == comp[j]) {
if(p[i][j] != 2) {
return 0;
}
} else if(p[i][j] != 0) {
return 0;
}
}
}
/*for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
cout<<b[i][j]<<" ";
}
cout<<endl;
}*/
build(b);
return 1;
}
/*int main() {
int n;
cin>>n;
vector<vector<int> > p(n);
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
int x;
cin>>x;
p[i].push_back(x);
}
}
construct(p);
}*/
