#include "supertrees.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
using namespace std;
typedef long long ll;
typedef long double ld;
ll n, k;
vector<vector<int>>a, d;
vector<int>c, fst, lst, gic;
vector<bool>used;
vector<bool>mej;
const int INF = 1e9 + 7;
int construct(vector<vector<int>> p) {
n = p.size();
a = p;
c.resize(n, INF);
fst.resize(n, -1);
lst.resize(n, -1);
gic.resize(n, INF);
d.resize(n);
for (int i = 0; i < n; i++) {
d[i].resize(n, 0);
}
used.resize(n, false);
mej.resize(n, true);
bool ent1 = true;
bool ent2 = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] != 0 && p[i][j] != 1) {
ent1 = false;
}
if (i != j && (p[i][j] != 0 && p[i][j] != 2)) {
ent2 = false;
}
}
}
if (ent1) {
int cur = 0;
for (int v = 0; v < n; v++) {
if (c[v] == INF) {
c[v] = cur++;
}
for (int to = 0; to < n; to++) {
if (p[v][to] == 1) {
if (c[to] != INF && c[to] != c[v]) {
return 0;
}
c[to] = c[v];
}
else {
if (c[to] == c[v])return 0;
}
}
}
for (int v = 0; v < n; v++) {
for (int to = v + 1; to < n; to++) {
if (c[to] == c[v]) {
d[v][to] = d[to][v] = 1;
break;
}
}
}
build(d);
return 1;
}
else if (ent2) {
int cur = 0;
for (int v = 0; v < n; v++) {
if (c[v] == INF) {
c[v] = cur++;
}
for (int to = 0; to < n; to++) {
if (p[v][to] == 2) {
if (c[to] != INF && c[to] != c[v]) {
return 0;
}
c[to] = c[v];
}
else if (p[v][to] == 0) {
if (c[to] == c[v])return 0;
}
}
}
for (int v = 0; v < n; v++) {
bool ok = false;
if (fst[c[v]] == -1) {
fst[c[v]] = v;
}
for (int to = v + 1; to < n; to++) {
if (c[to] == c[v]) {
d[v][to] = d[to][v] = 1;
ok = true;
break;
}
}
if (!ok) {
int to = fst[c[v]];
if (to != v) {
if (d[to][v] == 1)return 0;
d[to][v] = d[v][to] = 1;
}
}
}
build(d);
return 1;
}
else {
int cur = 0;
for (int v = 0; v < n; v++) {
if (c[v] == INF) {
c[v] = cur++;
}
for (int to = 0; to < n; to++) {
if (p[v][to] == 2 || p[v][to] == 1) {
if (c[to] != INF && c[to] != c[v]) {
return 0;
}
c[to] = c[v];
}
else if (p[v][to] == 0) {
if (c[to] == c[v])return 0;
}
}
}
for (int v = 0; v < n; v++) {
for (int to = 0; to < n; to++) {
if (to != v && p[v][to] == 1) {
mej[v] = false;
break;
}
}
}
for (int v = 0; v < n; v++) {
if (mej[v]) {
//cout << "Cikli mej a: " << v << endl;
used[v] = true;
if (fst[c[v]] == -1) {
fst[c[v]] = v;
}
lst[c[v]] = v;
for (int to = v + 1; to < n; to++) {
if (c[to] == c[v] && mej[to]) {
d[v][to] = d[to][v] = 1;
//cout << "Kpan: " << v << " " << to << endl;
break;
}
}
}
}
int curgic = 0;
for (int v = 0; v < n; v++) {
if (!used[v]) {
if (gic[v] == INF) {
gic[v] = curgic++;
}
for (int to = 0; to < n; to++) {
if (p[v][to] == 1) {
if (gic[to] != INF && gic[to] != gic[v]) {
return 0;
}
gic[to] = gic[v];
}
else if (p[v][to] == 2 && gic[to] == gic[v]) {
return 0;
}
}
}
}
for (int v = 0; v < n; v++) {
if (!used[v]) {
bool ok = false;
for (int to = v + 1; to < n; to++) {
if (c[to] == c[v] && gic[to] == gic[v]) {
d[v][to] = d[to][v] = 1;
//cout << "Kpan: " << v << " " << to << endl;
ok = true;
break;
}
}
if (!ok) {
//cout << "Verjiny " << c[v] << " guyni " << gic[v] << " toxi: " << v << endl;
int to = fst[c[v]];
if (to != v && to != -1) {
if (d[to][v] == 1)return 0;
d[to][v] = d[v][to] = 1;
//cout << "Kpan: " << v << " " << to << endl;
}
to = lst[c[v]];
if (to != v && to != -1 && to != fst[c[v]]) {
if (d[to][v] == 1)return 0;
d[to][v] = d[v][to] = 1;
//cout << "Kpan: " << v << " " << to << endl;
}
fst[c[v]] = v;
}
////cout << v << endl;
}
}
//return 1;
//cout << "3: " << c[3] << " " << gic[3] << " " << used[3] << endl;
build(d);
return 1;
}
}
/*
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
5 1 1 2 2 2 1 1 2 2 2 2 2 1 2 2 2 2 2 1 1 2 2 2 1 1
*/
