class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        int parent[] = new int[n+1];
        int rank[] = new int[n+1];
        makeset(parent, rank, n);
        
        for(int[] edge : dislikes) {
            int u = find(edge[0], parent);
            int v = find(edge[1], parent);
            
            if(u == v) {
                return false;
            }
            
            union(u, v, parent, rank);
        }
        
        return true;
    }
    
    private void makeset(int[] parent, int[] rank, int n) {
        for(int i=0 ; i<=n ; i++){
            parent[i] = i;
            rank[i] = 0;
        }
    }
    
    private int find(int node, int[] parent) {
        if(node == parent[node]) {
            return node;
        }
        
        return parent[node] = find(parent[node], parent);
    }
    
    private void union(int u, int v, int[] parent, int[] rank) {
        u = find(u, parent);
        v = find(v, parent);
        
        if(rank[u] < rank[v]) {
            parent[u] = v;
        }
        else if(rank[v] < rank[u]) {
            parent[v] = u;
        }
        else {
            parent[v] = u;
            rank[u]++;
        }
    }
}