#include <bits/stdc++.h> using namespace std; struct dsu { int n; vector<int> p, c; vector<vector<int>> cnt; dsu() {} dsu(int m) { n = m; p.assign(n, 0); c.assign(n, 1); cnt.assign(n, vector<int>(n)); iota(p.begin(), p.end(), 0); } int find(int x) { if (x == p[x]) return x; return p[x] = find(p[x]); } void merge(int a, int b) { p[b] = a; c[a] += c[b]; for (int i = 0; i < n; ++i) { if (find(i) == i) { cnt[a][i] += cnt[b][i]; cnt[i][a] += cnt[i][b]; } } } }; int n; dsu d; void initialize(int N) { n = N, d = dsu(n); } int hasEdge(int u, int v) { u = d.find(u); v = d.find(v); if (u == v) return 0; d.cnt[u][v]++; d.cnt[v][u]++; if (d.cnt[u][v] < d.c[u] * d.c[v]) return 0; d.merge(u, v); return 1; }