// Dwudzielność grafu
// Data: 24.11.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program test_bigraph;

// Typy dla dynamicznej tablicy
// list sąsiedztwa i kolejki
type
  PSLel = ^SLel;
  SLel =  record
    next : PSLel;
    v : integer;
  end;

  TList = array of PSLel;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      head : PSLel;
      tail : PSLel;

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      procedure push(v : integer);
      procedure pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor-tworzy pustą listę
//-------------------------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor-usuwa listę z pamięci
//---------------------------------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if head = nil then
    empty := true
  else
    empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then
    front := -MAXINT
  else
    front := head^.v;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push(v : integer);
var
  p : PSLel;
begin
  new(p);
  p^.next := nil;
  p^.v := v;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PSLel;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose(p);
  end;
end;

// Funkcja testuje dwudzielność grafu
// n - liczba wierzchołków grafu
// A - tablica list sąsiedztwa
//-----------------------------------
function isBipartite(n : integer;
                 var A : TList)
                       : boolean;
var
  Q : queue;
  C : array of integer;
  v, u, i : integer;
  p : PSLel;

begin
  // Tworzymy tablicę kolorów
  SetLength(C, n);
  for i := 0 to n-1 do
    C[i] := 0;
  // Tworzymy pustą kolejkę
  Q.init;
  // Przechodzimy przez
  // kolejne wierzchołki
  for i := 0 to n-1 do
    // Szukamy wierzchołka szarego
    if C[i] = 0 then
    begin
      // Wierzchołek startowy
      // kolorujemy na czerwono
      C[i] := 1;
      // i umieszczamy w kolejce
      Q.push(i);
      // Przejście BFS
      while Q.empty = false do
      begin
        // Pobieramy wierzchołek
        // z kolejki
        v := Q.front;
        // Pobrany wierzchołek
        // usuwamy z kolejki
        Q.pop;
        // Przeglądamy sąsiadów
        // wierzchołka v
        p := A[v];
        while p <> nil do
        begin
          // pobieramy z listy
          // sąsiedztwa numer
          // sąsiada
          u := p^.v;
          if C[u] = C[v] then
          begin
            SetLength(C, 0);
            Q.destroy;
            // Sąsiad ma ten
            // sam kolor
            Exit(false);
          end;
          // Jeśli wierzchołek
          // nie jest odwiedzony,
          if C[u] = 0 then
          begin
            // kolorujemy go na
            // kolor przeciwny
            C[u] := -C[v];
            // i umieszczamy
            // w kolejce
            Q.push(u);
          end;
          // Następny sąsiad
          p := p^.next;
        end;
      end;
    end;
  SetLength(C, 0);
  isBipartite := true;
end;

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

var
  n, m, i, v1, v2 : integer;
  p, r : PSLel;
  A : TList;

begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę
  // list sąsiedztwa
  SetLength(A, n);
  // Tablice wypełniamy
  // pustymi listami
  for i := 0 to n-1 do
    A[i] := nil;
  // Odczytujemy kolejne
  // definicje krawędzi
  for i := 0 to m-1 do
  begin
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(v1, v2);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako v2
    p^.v := v2;
    // Dodajemy go na początek
    // listy A[v1]
    p^.next := A[v1];
    A[v1] := p;
    // Krawędź w drugą stronę,
    // bo graf jest nieskierowany
    new(p);
    p^.v := v1;
    p^.next := A[v2];
    A[v2] := p;
  end;
  if isBipartite(n, A) then
    writeln('BIPARTITE GRAPH')
  else
    writeln('NOT A BIPARTITE GRAPH');
  // Usuwamy tablicę
  // list sąsiedztwa
  for i := 0 to n-1 do
  begin
    p := A[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;
  SetLength(A, 0);
end.

// Dwudzielność grafu
// Data: 24.11.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

const int MAXINT = 2147483647;

// Typy dla dynamicznej
// tablicy list sąsiedztwa
// i kolejki
struct SLel
{
  SLel * next;
  int v;
};

// Typ obiektowy queue
//--------------------
class queue
{
  private:
    SLel * head;
    SLel * tail;

  public:
    queue(); // konstruktor
    ~queue(); // destruktor
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor
//------------
queue::queue()
{
  head = tail = nullptr;
}

// Destruktor
//-----------
queue::~queue()
{
  while(head) pop();
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty(void)
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front (void)
{
  if(head)
    return head->v;
  else
    return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push(int v)
{
  SLel * p = new SLel;
  p->next = nullptr;
  p->v = v;
  if(tail)
    tail->next = p;
  else
    head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop(void)
{
  if(head)
  {
    SLel * p = head;
    head = head->next;
    if(!head)
      tail = nullptr;
    delete p;
  }
}

// Funkcja testuje dwudzielność
// grafu
// n - liczba wierzchołków grafu
// A - tablica list sąsiedztwa
//------------------------------
bool isBipartite(int n,
                 SLel ** A)
{
  queue Q;
  int * C;
  int v, u, i;
  SLel * p;

  // Tworzymy tablicę kolorów
  C = new int[n];
  for(i = 0; i < n; i++)
    C[i] = 0;

  // Przechodzimy przez
  // kolejne wierzchołki
  for(i = 0; i < n; i++)
    // Szukamy wierzchołka
    // szarego
    if(!C[i])
    {
      // Wierzchołek startowy
      // kolorujemy na czerwono
      C[i] = 1;
      // i umieszczamy w kolejce
      Q.push(i);
      // Przejście BFS
      while(!Q.empty())
      {
        // Pobieramy wierzchołek
        // z kolejki
        v = Q.front();
        // Pobrany wierzchołek
        // usuwamy z kolejki
        Q.pop();
        // Przeglądamy sąsiadów
        // wierzchołka v
        for(p = A[v]; p; p = p->next)
        {
          // pobieramy z listy
          // sąsiedztwa numer sąsiada
          u = p->v;
          if(C[u] == C[v])
          {
            delete [] C;
            // Sąsiad ma ten sam kolor
            return false;
          }

          // Jeśli wierzchołek
          // nie jest odwiedzony,
          if(!C[u])
          {
            // kolorujemy go
            // na kolor przeciwny
            C[u] = -C[v];
            // i umieszczamy w kolejce
            Q.push(u);
          }
        }
      }
    }
  delete [] C;
  return true;
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int n, m, i, v1, v2;
  SLel * p, * r, ** A;

  // Czytamy liczbę
  // wierzchołków
  // i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę
  // list sąsiedztwa
  A = new SLel * [n];
  // Tablicę wypełniamy
  // pustymi listami
  for(i = 0; i < n; i++)
    A[i] = nullptr;
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> v1 >> v2;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako v2
    p->v = v2;
    // Dodajemy go
    // na początek
    // listy A[v1]
    p->next = A[v1];
    A[v1] = p;
    // Krawędź w drugą stronę,
    // bo graf jest nieskierowany
    p = new SLel;
    p->v = v1;
    p->next = A[v2];
    A[v2] = p;
  }
  if(isBipartite(n, A))
    cout << "BIPARTITE GRAPH";
  else
    cout << "NOT A BIPARTITE GRAPH";
  cout << endl;
  // Usuwamy tablicę
  // list sąsiedztwa
  for(i = 0; i < n; i++)
  {
    p = A[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] A;
  return 0;
}

' Testowanie dwudzielności grafu
' Data: 24.11.2013
' (C)2013 mgr Jerzy Wałaszek
'-------------------------------

Const MAXINT = 2147483647

' Typy dla dynamicznej tablicy
' list sąsiedztwa i kolejki
Type SLel
  next As SLel Ptr
  v As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As SLel Ptr
    tail As SLel Ptr

  Public:
    Declare Constructor
    Declare Destructor
    Declare Function empty As Integer
    Declare Function front As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor
'------------
Constructor queue
  head = 0
  tail = 0
End Constructor

' Destruktor
'-----------
Destructor queue
  While empty = 0
    pop
  Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->v
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal v As Integer)
  Dim p As SLel Ptr
  p = new SLel
  p->next = 0
  p->v = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop
  Dim p As SLel Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

' Funkcja testuje dwudzielność grafu
' n - liczba wierzchołków grafu
' A - tablica list sąsiedztwa
'-----------------------------------
Function isBipartite(ByVal n As integer, _
                 ByVal A As SLel Ptr Ptr) _
                         As Integer
  Dim As queue Q
  Dim As Integer Ptr C
  Dim As Integer v, u, i
  Dim As SLel Ptr p

  ' Tworzymy tablicę kolorów
  C = New Integer [n]
  For i = 0 To n-1
    C[i] = 0
  Next
  ' Przechodzimy przez kolejne wierzchołki
  For i = 0 To n-1
    ' Szukamy wierzchołka szarego
    If C[i] = 0 Then
      ' Wierzchołek startowy
      ' kolorujemy na czerwono
      C[i] = 1
      ' i umieszczamy w kolejce
      Q.push(i)
      ' Przejście BFS
      While Q.empty = 0
        ' Pobieramy wierzchołek z kolejki
        v = Q.front
        ' Pobrany wierzchołek
        ' usuwamy z kolejki
        Q.pop
        p = A[v]
        ' Przeglądamy sąsiadów wierzchołka v
        While p <> 0
          ' pobieramy z listy sąsiedztwa
          ' numer sąsiada
          u = p->v
          If C[u] = C[v] Then
            Delete [] C
            ' Sąsiad ma ten sam kolor
            Return 0
          End If
          ' Jeśli wierzchołek nie
          ' jest odwiedzony, 
          If C[u] = 0 Then
            ' kolorujemy go
            ' na kolor przeciwny
            C[u] = -C[v]
            ' i umieszczamy w kolejce
            Q.push(u)
          End If
          ' Następny wierzchołek
          p = p->next
        Wend
      Wend
    End If
  Next
  Delete [] C
  Return 1
End Function

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer n, m, i, v1, v2
Dim As SLel Ptr p, r
Dim As SLel Ptr Ptr A

Open Cons For Input As #1
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę list sąsiedztwa
A = new SLel Ptr [n]
' Tablicę wypełniamy pustymi listami
For i = 0 To n-1
  A[i] = 0
Next
' Odczytujemy kolejne definicje krawędzi
For i = 0 To m -1
  ' Wierzchołek startowy i końcowy krawędzi
  Input #1, v1, v2
  ' Tworzymy nowy element
  p = new SLel
  ' Numerujemy go jako v2
  p->v = v2
  ' Dodajemy go na początek listy A[v1]
  p->next = A[v1]
  A[v1] = p
  ' Krawędź w drugą stronę,
  ' bo graf jest nieskierowany
  p = new SLel
  p->v = v1
  p->next = A[v2]
  A[v2] = p
Next
Close #1
If isBipartite(n, A) Then
  Print "BIPARTITE GRAPH"
Else
  Print "NOT A BIPARTITE GRAPH"
EndIf
' Usuwamy tablicę list sąsiedztwa
For i = 0 To n-1
  p = A[i]
  While p
    r = p
    p = p->next
    Delete r
  Wend
Next
Delete [] A
End

# Testowanie dwudzielności grafu
# Data: 21.01.2025
# (C)2025 mgr Jerzy Wałaszek
#-------------------------------

MAXINT = 2147483647

# Klasa dla dynamicznej tablicy
# list sąsiedztwa i kolejki
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0


# Klasa Queue
#------------
class Queue:
    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None


    # Destruktor
    def __del__(self):
        while self.head:
            self.pop()


    # Sprawdza, czy kolejka jest pusta
    def empty(self):
        return not self.head


    # Zwraca początek kolejki.
    # Wartość specjalna to -MAXINT
    def front(self):
        global MAXINT
        if not self.head:
            return -MAXINT
        else:
            return self.head.v


    # Zapisuje do kolejki
    def push(self, v):
        p = SLel()
        p.next = None
        p.v = v
        if not self.tail:
            self.head = p
        else:
            self.tail.next = p
        self.tail = p


    # Usuwa z kolejki
    def pop(self):
        if self.head:
            self.head = self.head.next
            if not self.head:
                self.tail = None


# Funkcja testuje dwudzielność grafu
# n - liczba wierzchołków grafu
# a - tablica list sąsiedztwa
def is_bipartite(n, a):
    q = Queue()
    # Tworzymy tablicę kolorów
    c = [0] * n
    # Przechodzimy przez
    # kolejne wierzchołki
    for i in range(n):
        # Szukamy wierzchołka szarego
        if c[i] == 0:
            # Wierzchołek startowy
            # kolorujemy na czerwono
            c[i] = 1
            # i umieszczamy w kolejce
            q.push(i)
            # Przejście BFS
            while not q.empty():
                # Pobieramy wierzchołek
                # z kolejki
                v = q.front()
                # Pobrany wierzchołek
                # usuwamy z kolejki
                q.pop()
                p = a[v]
                # Przeglądamy sąsiadów
                # wierzchołka v
                while p:
                    # pobieramy z listy
                    # sąsiedztwa
                    # numer sąsiada
                    u = p.v
                    if c[u] == c[v]:
                        del c
                        # Sąsiad ma ten
                        # sam kolor
                        return False
                    # Jeśli wierzchołek
                    # nie jest odwiedzony, 
                    if not c[u]:
                        # kolorujemy go
                        # na kolor
                        # przeciwny
                        c[u] = -c[v]
                        # i umieszczamy
                        # w kolejce
                        q.push(u)
                    # Następny wierzchołek
                    p = p.next
    del c
    return True

# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę list sąsiedztwa
a = [None] * n
# Odczytujemy kolejne definicje krawędzi
for i in range(m):
    # Wierzchołek startowy
    # i końcowy krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako v2
    p.v = v2
    # Dodajemy go na początek listy a[v1]
    p.next = a[v1]
    a[v1] = p
    # Krawędź w drugą stronę,
    # bo graf jest nieskierowany
    p = SLel()
    p.v = v1
    p.next = a[v2]
    a[v2] = p
if is_bipartite(n, a):
    print("BIPARTITE GRAPH")
else:
    print("NOT A BIPARTITE GRAPH")
# Usuwamy tablicę list sąsiedztwa
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a