//#include "grader.cpp"
#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define pb(a) push_back(a)
const int N = 1e3+5;
vector<vector<int>> p1, b1;
int n1, timer, par[N], used[N], time1[N];
vector <int> c;
void dfs(int u){
c.pb(u);
used[u] = 1;
par[u] = u;
time1[u] = timer;
for(int i=0;i<n1;i++){
if(used[i]) continue;
if(p1[u][i] == 1){
used[i] = 1;
par[i] = u;
time1[i] = timer;
b1[u][i] = b1[i][u] = 1;
}
}
for(int i=0;i<n1;i++){
if(used[i]) continue;
if(p1[u][i] == 2) dfs(i);
}
}
int construct(vector<vector<int>> P) {
p1 = P;
n1 = p1.size();
b1.resize(n1, vector<int>(n1, 0));
for(int i=0;i<n1;i++){
if(used[i]) continue;
dfs(i);
if(c.size() == 2) return 0;
else if(c.size() > 2){
int s = c.size() - 1;
for(int j=0;j<s; j++){
b1[c[j]][c[j+1]] = 1;
b1[c[j+1]][c[j]] = 1;
}
b1[c[0]][c[s]] = 1;
b1[c[s]][c[0]] = 1;
}
timer ++;
c.clear();
}
for(int i=0;i<n1;i++){
for(int j=0;j<n1;j++){
if(par[i] == par[j] && p1[i][j] != 1) return 0;
if(time1[i] == time1[j] && par[i] != par[j] && p1[i][j] != 2) return 0;
if(time1[i] != time1[j] && p1[i][j]) return 0;
}
}
build(b1);
return 1;
}
/*
5
0 2 2 2 2
2 0 2 2 2
2 2 0 2 2
2 2 2 0 2
2 2 2 2 0
3
1 2 2
2 1 2
2 2 1
4
1 1 2 2
1 1 2 2
2 2 1 2
2 2 2 1
5
1 2 2 2 0
2 1 2 2 0
2 2 1 2 0
2 2 2 1 0
0 0 0 0 1
*/
