Bipartite

/*
    Task    : Bipartite Graph Check
    Author  : Phumipat C. [MAGCARI]
    Language: C++
    Created : 30 July 2022 [11:03]
*/
#include<bits/stdc++.h>
using namespace std;
vector<int > g[100010];
int color[100010];
//0 - uncolor   1,2 - colored
bool dfs(int now,int c){
    //base case
    if(color[now]){
        if(color[now] == c) return true;
        else                return false;
    }

    //process
    color[now] = c;
    for(auto x:g[now]){
        // 3 - c
        if(!dfs(x,3-c))
            return false;
    }
    return true;
}
int main(){
    int n,m,u,v;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d %d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    if(dfs(1,1)){
        printf("Bipatite!");
    }else{
        printf("Not Bipartite!");
    }
    return 0;
}