int m, adj[1505][1505]; struct disj{ int pa[1505]; void init(int n) { for(int i=0; i<n; i++) pa[i] = i; } int find(int x){ return pa[x] = (pa[x] == x ? x : find(pa[x])); } void uni(int p, int q){ p = find(p); q = find(q); pa[q] = p; } }disj; void initialize(int n){ m = n; } bool bad(){ disj.init(m); for (int i=0; i<m; i++) { for (int j=i+1; j<m; j++) { if(!adj[i][j]) disj.uni(i,j); } } for (int i=1; i<m; i++) { if(disj.find(0) != disj.find(i)) return 1; } return 0; } int hasEdge(int u, int v){ adj[u][v] = adj[v][u] = 1; if(bad()) adj[u][v] = adj[v][u] = 0; return !adj[u][v]; }