#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define ll long long
#define endl "\n"
const int MOD = 998244353;
/*
int n2;
std::vector<std::vector<int>> p;
std::vector<std::vector<int>> b;
bool called = false;
static void check(bool cond, std::string message) {
if (!cond) {
cout << message << endl;
exit(0);
}
}
void build(std::vector<std::vector<int>> _b) {
check(!called, "build is called more than once");
called = true;
check((int)_b.size() == n2, "Invalid number of rows in b");
for (int i = 0; i < n2; i++) {
check((int)_b[i].size() == n2, "Invalid number of columns in b");
}
b = _b;
}*/
void DFS(int x, vector<int>& num, int curr, int type, vector<vector<int>>& edges){
if(curr == (int)num.size() - 1){
if(type == 1) return;
else{
edges[num[curr]][x] = 1;
edges[x][num[curr]] = 1;
return;
}
}
edges[num[curr]][num[curr + 1]] = 1;
edges[num[curr + 1]][num[curr]] = 1;
DFS(x, num, curr + 1, type, edges);
}
int construct(vector<vector<int>> v){
int n = (int)v[0].size();
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(v[i][j] == 3) return 0;
}
}
vector<bool> done(n, 0);
vector<vector<int>> edges(n, vector<int> (n, 0));
for(int i = 0; i < n; i++){
if(done[i]) continue;
vector<int> two;
vector<int> one = {i};
set<int> cc;
cc.insert(i);
done[i] = 1;
for(int j = 0; j < n; j++){
if(i == j) continue;
if(v[i][j] == 1) {one.push_back(j); cc.insert(j);}
else if(v[i][j] == 2) {two.push_back(j); cc.insert(j);}
}
for(int x : two){
done[x] = 1;
for(int j = 0; j < n; j++){
if(x == j) continue;
bool good = cc.count(j);
if(good == false && v[x][j] > 0) return 0;
//if(good == true && v[x][j] != max(v[i][j], v[i][x])) return 0;
}
}
for(int x : one){
done[x] = 1;
for(int j = 0; j < n; j++){
if(x == j) continue;
bool good = cc.count(j);
if(good == false && v[x][j] > 0) return 0;
if(good == true && v[x][j] != max(v[i][j], v[i][x])) return 0;
}
}
if(two.size() == 0){
DFS(i, one, 0, 1, edges);
}else{
vector<vector<int>> circle;
circle.push_back(one);
vector<bool> assigned(two.size(), 0);
for(int j = 0; j < two.size(); j++){
if(assigned[j]) continue;
assigned[j] = 1;
one.resize(0);
one.push_back(two[j]);
for(int q = 0; q < two.size(); q++){
if(q == j) continue;
if(v[two[j]][two[q]] == 1){
if(assigned[q]) return 0;
assigned[q] = 1;
one.push_back(two[q]);
}
}
circle.push_back(one);
}
if((int)circle.size() < 3) return 0;
for(auto t : circle){
DFS(i, t, 0, 1, edges);
}
int sz = (int)circle.size();
for(int j = 0; j < sz; j++){
edges[circle[j][0]][circle[(j + 1) % sz][0]] = 1;
edges[circle[(j + 1) % sz][0]][circle[j][0]] = 1;
}
}
}
build(edges);
return 1;
}
/*
int main() {
cin >> n2;
p.resize(n2);
for (int i = 0; i < n2; i++) {
p[i].resize(n2);
}
for (int i = 0; i < n2; i++) {
for (int j = 0; j < n2; j++) {
cin >> p[i][j];
}
}
int possible = construct(p);
check(possible == 0 || possible == 1, "Invalid return value of construct");
if (possible == 1) {
check(called, "construct returned 1 without calling build");
} else {
check(!called, "construct called build but returned 0");
}
cout << possible << endl;
if (possible == 1) {
for (int i = 0; i < n2; i++) {
for (int j = 0; j < n2; j++) {
if (j) {
cout << " ";
}
cout << b[i][j];
}
printf("\n");
}
}
}*/
