#include "supertrees.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void road(vector <vector<int> >&ans, int a, int b) {
ans[a][b] = ans[b][a] = 1;
}
int n;
const int N = 1e3 + 5;
vector <int> par(N);
// vector <vector <int> > par(N);
int find(int a) {
if (par[a] == a) return a;
return par[a] = find(par[a]);
}
bool merge(int a, int b, vector <vector<int> >& p) {
int A = find(a), B = find(b);
par[B] = A;
// cout << a << ' ' << b << " " << A << ' ' << B << '\n';
p[A][B] = p[B][A] = 2;
// cout << "A: ";
// for (auto el : p[A]) cout << el << ' ';
// cout << "\n";
// cout << "B: ";
// for (auto el : p[B]) cout << el << ' ';
// cout << "\n";
if (p[A] != p[B]) return 0;
for (int i = 0; i < n; i++) {
if (p[B][i] > 0) p[B][i] = p[i][B] = 0;
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) cout << p[i][j] << ' ';
// cout << "\n";
// }
return 1;
}
int construct(vector <vector<int> > p) {
n = p.size();
vector <vector <int> > answer(n, vector <int>(n, 0)), paths(n);
for (int i = 0; i < n; i++) par[i] = i, p[i][i] = 2;
// cout << "HERE\n";
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (p[i][j] == 3) return 0;
}
// cout << "HERE\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 1) {
if (!merge(i, j, p)) {
return 0;
}
road(answer, i, j);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (p[i][j] == 2) {
paths[i].push_back(j);
}
}
}
vector <bool> vis(n+5, 0);
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
vector <int> child, tmp;
for (auto el : paths[i]) child.push_back(el);
while(child.size() > 1) {
if (child.size() & 1) child.push_back(child.back());
tmp.clear();;
int k = child.size();
for (int j = 0; j < k; j+=2) {
if (paths[child[j]] != paths[child[j+1]]) {
return 0;
}
tmp.push_back(child[j]);
}
swap(child, tmp);
}
child.clear();
for (auto el : paths[i]) child.push_back(el);
// cout << i << ": ";
// for (auto el : child) cout << el << ' ';
// cout << '\n';
int m = paths[i].size();
if (m < 3) return 0;
for (int j = 0; j < m; j++) {
vis[child[j]] = 1;
road(answer, child[j], child[(j+1)%m]);
}
}
for (int i = 0; i < n; i++) answer[i][i] = 0;
build(answer);
return 1;
}
// g++ -std=gnu++17 -O2 -Wall -pipe -static -o supertrees grader.cpp supertrees.cpp
