/*------------------------------------------------------------------------------
 * problem012.cc: Bicoloring
**----------------------------------------------------------------------------*/

/* Copyright (c) 2009 Peter Bui. All Rights Reserved.
 *
 * Peter Bui <pbui@cse.nd.edu>
 *
**------------------------------------------------------------------------------
 * Includes
**----------------------------------------------------------------------------*/

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

/*------------------------------------------------------------------------------
 * Constants
**----------------------------------------------------------------------------*/

enum {
    COLOR_BLACK,
    COLOR_RED,
    COLOR_NONE
};

/*------------------------------------------------------------------------------
 * Data Structures
**----------------------------------------------------------------------------*/

typedef struct {
    size_t nvertices;
    size_t nedges;
    vector< vector<int> > edges;
    vector<int> colors;
} Graph;

/*------------------------------------------------------------------------------
 * Functions
**----------------------------------------------------------------------------*/

static bool
read_graph(Graph &g)
{
    int v0, v1;

    cin >> g.nvertices;
    if (g.nvertices == 0)
	return (false);

    g.edges.clear();
    g.edges.resize(g.nvertices);

    cin >> g.nedges;
    for (size_t i = 0; i < g.nedges; i++) {
	cin >> v0 >> v1;
	g.edges[v0].push_back(v1);
	g.edges[v1].push_back(v0);
    }

    g.colors.clear();
    g.colors.resize(g.nvertices, COLOR_NONE);

    return (true);
}

static bool
color_vertex(Graph &g, int v, int c)
{
    if (g.colors[v] == COLOR_NONE) {
	g.colors[v] = c;
	for (size_t i = 0; i < g.edges[v].size(); i++)
	    if (!color_vertex(g, g.edges[v][i], (c + 1) % COLOR_NONE))
		return (false);
	return (true);
    } else if (g.colors[v] == c) {
	return (true);
    } else {
	return (false);
    }
}

static bool
is_bicolorable(Graph &g)
{
    return (color_vertex(g, 0, COLOR_RED));
}

/*------------------------------------------------------------------------------
 * Main Execution
**----------------------------------------------------------------------------*/

int
main(int argc, char* argv[]) 
{
    Graph g;

    while (read_graph(g)) 
	cout << (is_bicolorable(g) ? "BICOLORABLE" : "NOT BICOLORABLE") << endl;

    return (EXIT_SUCCESS);
}

/*------------------------------------------------------------------------------
 * vim: sts=4 sw=4 ts=8 ft=cpp
**----------------------------------------------------------------------------*/