10004 - Bicoloring

#include <bits/stdc++.h>
#define  pb     push_back
#define  MAX    10000007
#define  mod    100000007
#define  read   freopen("input.txt","r",stdin);
#define  write  freopen("output.txt","w",stdout);
#define  inf   (1<<30)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

bool BFS(int s);

vector<int>graph[300];
queue<int>Q;
bool mark[300];
map<int,string>mp;

int main()
{

    int n;
  //  read;
 //   write;
    while(~scanf("%d",&n))
    {
        if(n==0) break;
        int edge;
        scanf("%d",&edge);
        memset(mark,false,sizeof(mark));
        mp.clear();
        for(int i=0; i<300; i++) graph[i].clear();
        int start;
        for(int i=0; i<edge; i++)
        {
            int a,b;
            scanf("%d %d",&a,&b);
            start=a;
            graph[a].pb(b);
            graph[b].pb(a);

        }
        while(!Q.empty()) Q.pop();
        if( BFS(start)==true) puts("BICOLORABLE.");
        else puts("NOT BICOLORABLE.");

    }


    return 0;
}

bool BFS(int start)
{
    Q.push(start);
    mp[start]="black";
   // int cnt=0;

    while(!Q.empty())
    {
        int node=Q.front();
        Q.pop();
        mark[node]=true;
        int len=graph[node].size();
        for(int i=0; i<len; i++)
        {
            int n=graph[node][i];

            if(mark[n]==false)
            {
                Q.push(n);

                if(mp[node]=="black") mp[n]="red";
                else mp[n]="black";
            }
            else
            {
                if(mp[node]==mp[n]) return false;

            }

        }

    }
    return true;

}