We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.

Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.

&nbsp;
Example 1:

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4] and group2 [2,3].


Example 2:

Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false


Example 3:

Input: n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false


&nbsp;
Constraints:


	1 &lt;= n &lt;= 2000
	0 &lt;= dislikes.length &lt;= 104
	dislikes[i].length == 2
	1 &lt;= dislikes[i][j] &lt;= n
	ai &lt; bi
	All the pairs of dislikes are unique.


class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        def dfs(i, c):
            if color[i] != 0:
                if color[i] != c:
                    return False
                return True

            color[i] = c
            for u in e[i]:
                if not dfs(u, 3 - c):
                    return False
            return True

        e = [[] for _ in range(n)]
        for u, v in dislikes:
            u -= 1
            v -= 1
            e[u].append(v)
            e[v].append(u)
        color = [0] * n
        for i in range(n):
            if color[i] == 0:
                if not dfs(i, 1):
                    return False
        return True
class Solution {
    int[] rank;
    int[] parent;
    int[] rival;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        rank = new int[n+1];
        rival = new int[n+1];
        parent = new int[n+1];
        for(int i = 1;i <= n;i++){
            rank[i] = 1;
            parent[i] = i;
        }
        for(int[] dis : dislikes){
            int x = dis[0], y = dis[1];
            if(find(x) == find(y))
                return false;
            if(rival[x] != 0)
                union(rival[x], y);
            else
                rival[x] = y;
            if(rival[y] != 0)
                union(rival[y], x);
            else
                rival[y] = x;
        }
        return true;
    }
    public int find(int x){
        if(parent[x] == x)
            return x;
        return parent[x] = find(parent[x]);
    }
    public void union(int x, int y){
        int x_set = find(x);
        int y_set = find(y);
        if(x_set == y_set)
            return;
        if(rank[x_set] < rank[y_set])
            parent[x_set] = y_set;
        else if(rank[y_set] < rank[x_set])
            parent[y_set] = x_set;
        else{
            parent[x_set] = y_set;
            rank[y_set]++;
        }
    }
}
class Solution {
public:
    
    bool dfs(vector<int>adj[], vector<int>& color, int node){
        for(auto it: adj[node]){ //dfs over adjacent nodes
            if(color[it]==-1){ //not visited yet
                color[it]=1-color[node]; //set different color of adjacent nodes 
                if(!dfs(adj,color,it)) return false;
            }
            else if(color[it]!=1-color[node]) return false; //if adjacent nodes have same color
        }
        return true;
    }
    
    
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        vector<int>adj[n+1];
        for(int i=0;i<dislikes.size();i++){//undirected graph
            adj[dislikes[i][0]].push_back(dislikes[i][1]);
            adj[dislikes[i][1]].push_back(dislikes[i][0]);
        }
        vector<int>color(n+1,-1); //-1 i.e. not visited yet
        for(int i=1;i<=n;i++){
            if(color[i]==-1){
                color[i]=0;
                if(!dfs(adj,color,i)) return false;
            }
        }
        return true;
    }
};
var possibleBipartition = function(n, dislikes) {
    const g = new Map();
    dislikes.forEach(([a, b]) => {
        const aDis = g.get(a) || [];
        const bDis = g.get(b) || [];
        g.set(a, aDis.concat(b));
        g.set(b, bDis.concat(a));
    });
    
    const vis = new Array(n+1).fill(false);
    const col = new Array(n+1).fill(-1);
    
    const dfs = (n, c = 0) => {
        if(vis[n]) return true;
        
        col[n] = c;
        vis[n] = true;
        
        const nodes = g.get(n) || [];
        for(let node of nodes) {
            if(!vis[node]) {
                if(!dfs(node, 1 - c)) return false;
            }
            
            if(node != n && col[node] == c) return false;
        }
        
        return true;
    };
    
    let canBi = true;
    for(let i = 1; i <= n; i++) {
        canBi &= dfs(i);
    }
    return canBi;
};
Possible Bipartition