// Badanie, czy graf zawiera
// cykl lub ścieżkę Eulera
// Data: 4.01.2014
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program eulercp;

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

TList = array of PSLel;

// Definicja typu obiektowego Stack
//---------------------------------
Stack = object
  private
    // lista przechowująca stos
    S : PSLel;
  public
    constructor init;
    destructor destroy;
    function   empty : boolean;
    function   top : integer;
    procedure  push(v : integer);
    procedure  pop;
end;

// Konstruktor
//------------
constructor Stack.init;
begin
  S := nil;
end;

// Destruktor
//-----------
destructor Stack.destroy;
begin
  while S <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function Stack.empty : boolean;
begin
  if S = nil then
    empty := true
  else
    empty := false;
end;

// Zwraca liczbę ze szczytu stosu
//-------------------------------
function Stack.top : integer;
begin
  if S <> nil then
    top := S^.v
  else
    top := -MAXINT;
end;

// Umieszcza dane na stosie
//-------------------------
procedure Stack.push(v : integer);
var
  e : PSLel;
begin
  new(e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure Stack.pop;
var
  e :PSLel;
begin
  if S <> nil then
  begin
    e := S;
    S := S^.next;
    dispose(e);
  end;
end;

// Funkcja bada graf pod kątem
// posiadania cyklu lub
// ścieżki Eulera
// n - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// Wynik:
// 0 - graf nie zawiera ścieżki
//     lub cyklu Eulera
// 1 - graf zawiera ścieżkę Eulera
// 2 - graf zawiera cykl Eulera
//---------------------------------
function isEulerian(n : integer;
             var graf : TList)
                      : integer;
var
  no, nc, i, v, u : integer;
  S : Stack;
  vs : array of boolean;
  p : PSLel;

begin
  // Szukamy pierwszego
  // wierzchołka z sąsiadami
  i := 0;
  while (i < n) and
        (graf[i] = nil) do
    inc(i);
  // Graf nie ma krawędzi
  if i = n then Exit(1);
  // Tworzymy dynamicznie
  // tablicę odwiedzin
  SetLength(vs, n);
  // Wypełniamy ją wartościami false
  for v := 0 to n-1 do
    vs[v] := false;
  // Tworzymy stos
  S.init;
  // Zerujemy licznik wierzchołków
  // o stopniu nieparzystym
  no := 0;
  // Wierzchołek startowy na stos
  S.push(i);
  // oznaczamy go jako odwiedzony
  vs[i] := true;
  // Uruchamiamy przejście DFS,
  // aby wyznaczyć spójną składową
  // zawierającą wierzchołek startowy
  // oraz policzyć stopnie wierzchołków
  // i wyznaczyć liczbę wierzchołków
  // o stopniach nieparzystych
  while S.empty = false do
  begin
    // Pobieramy do v wierzchołek
    // ze stosu
    v := S.top;
    // Pobrany wierzchołek usuwamy
    // ze stosu
    S.pop;
    // Licznik sąsiadów na zero
    nc := 0;
    // Przeglądamy sąsiadów
    // wierzchołka v
    p := graf[v];
    while p <> nil do
    begin
      // Zwiększamy licznik sąsiadów
      inc(nc);
      u := p^.v;
      // Szukamy nieodwiedzonych
      // sąsiadów
      if not vs[u] then
      begin
        // Oznaczamy ich
        // jako odwiedzonych
        vs[u] := true;
        // i umieszczamy na stosie
        S.push(u);
      end;
      // Przechodzimy do następnego
      // sąsiada na liście
      p := p^.next;
    end;
    // Nieparzysta liczba sąsiadów?
    if nc mod 2 = 1 then inc(no);
  end;
  // Przeglądamy pozostałe
  // wierzchołki grafu
  for v := i+1 to n-1 do
    if (vs[v] = false) and
       (graf[v] <> nil) then
    begin
      // Usuwamy tablicę odwiedzin
      SetLength(vs, 0);
      // graf nie jest spójny
      Exit(0);
    end;
  // Usuwamy tablicę odwiedzin
  SetLength(vs, 0);
  // Graf zawiera cykl Eulera
  if no = 0 then Exit(2);
   // Graf zawiera ścieżkę Eulera
  if no = 2 then Exit(1);
  // Graf nie posiada ścieżki
  // lub cyklu Eulera
  Exit(0);
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);
  // Tablicę 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;
  writeln;
  case isEulerian(n, A) of
    0: writeln('NOT AN EULERIAN GRAPH');
    1: writeln('SEMI-EULERIAN GRAPH');
    2: writeln('EULERIAN GRAPH');
  end;
  // 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.

// Badanie, czy graf zawiera
// cykl lub ścieżkę Eulera
// Data: 4.01.2014
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

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

const int MAXINT = 2147483647;

class Stack
{
  private:
    // lista przechowująca stos
    SLel * S;

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

//---------------------
// Metody obiektu Stack
//---------------------

// Konstruktor
//------------
Stack::Stack()
{
  S = nullptr;
}

// Destruktor
//-----------
Stack::~Stack()
{
  while(S) pop();
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool Stack::empty(void)
{
  return !S;
}

// Zwraca szczyt stosu
//--------------------
int Stack::top(void)
{
  if(S) return S->v;
  return -MAXINT;
}

// Zapisuje na stos
//-----------------
void Stack::push(int v)
{
  SLel * e = new SLel;
  e->v = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void Stack::pop(void)
{
  if(S)
  {
    SLel * e = S;
    S = S->next;
    delete e;
  }
}

// Funkcja bada graf pod kątem
// posiadania cyklu lub ścieżki
// Eulera
// n - liczba wierzchołków w grafie
// graf - tablica list sąsiedztwa
// Wynik:
// 0 - graf nie zawiera ścieżki
//     lub cyklu Eulera
// 1 - graf zawiera ścieżkę Eulera
// 2 - graf zawiera cykl Eulera
//----------------------------------
int isEulerian(int n,
               SLel ** graf)
{
  int no, nc, i, v, u;
  Stack S;
  bool * vs;
  SLel *p;

  // Szukamy pierwszego wierzchołka
  // z sąsiadami
  for(i = 0; i < n && !graf[i]; i++);
  // Graf nie ma krawędzi
  if(i == n) return 1;
  // Tworzymy dynamicznie
  // tablicę odwiedzin
  vs = new bool [n];
  // Wypełniamy ją wartościami false
  for(v = 0; v < n; v++)
    vs[v] = false;
  // Zerujemy licznik wierzchołków
  // o stopniu nieparzystym
  no = 0;
  // Wierzchołek startowy na stos
  S.push(i);
  // oznaczamy go jako odwiedzony
  vs[i] = true;
  // Uruchamiamy przejście DFS,
  // aby wyznaczyć spójną składową
  // zawierającą wierzchołek startowy
  // oraz policzyć stopnie wierzchołków
  // i wyznaczyć liczbę wierzchołków
  // o stopniach nieparzystych

  while(!S.empty())
  {
    // Pobieramy do v wierzchołek
    // ze stosu
    v = S.top();
    // Pobrany wierzchołek usuwamy
    // ze stosu
    S.pop();
    // Licznik sąsiadów na zero
    nc = 0;
    // Przeglądamy sąsiadów
    // wierzchołka v
    for(p = graf[v]; p; p = p->next)
    {
      // Zwiększamy licznik sąsiadów
      nc++;
      u = p->v;
      // Szukamy nieodwiedzonych sąsiadów
      if(!vs[u])
      {
        // Oznaczamy ich
        // jako odwiedzonych
        vs[u] = true;
        // i umieszczamy na stosie
        S.push(u);
      }
    }
    // Nieparzysta liczba sąsiadów?
    if(nc % 2 == 1) no++;
  }
  // Przeglądamy pozostałe
  // wierzchołki grafu
  for(v = i = 1; v < n; v++)
    if(!vs[v] && graf[v])
    {
      // Usuwamy tablicę odwiedzin
      delete [] vs;
      // graf nie jest spójny
      return 0;
    }
  // Usuwamy tablicę odwiedzin
  delete [] vs;
  // Graf zawiera cykl Eulera
  if(!no) return 2;
  // Graf zawiera ścieżkę Eulera
  if(no == 2) return 1;
  // Graf nie posiada ścieżki
  // lub cyklu Eulera
  return 0;
}

// **********************
// *** 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;
  }
  cout << endl;
  switch(isEulerian(n, A))
  {
    case 0: cout << "NOT AN EULERIAN GRAPH\n";
            break;
    case 1: cout << "SEMI-EULERIAN GRAPH\n";
            break;
    case 2: cout << "EULERIAN GRAPH\n";
            break;
  }
  // 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;
}

' Badanie, czy graf zawiera
' cykl lub ścieżkę Eulera
' Data: 4.01.2014
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Typy dla dynamicznej
' tablicy list sąsiedztwa i stosu

Type SLel
  next As SLel Ptr
  v As Integer
End Type

Type Stack
  Private:
    ' lista zawierająca stos
    S As SLel Ptr
  
  Public:
    Declare Constructor
    Declare Destructor
    Declare Function empty As Integer
    Declare Function top As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop
End Type

Const MAXINT = 2147483647

'---------------------
' Metody obiektu Stack
'---------------------

' Konstruktor
'------------
Constructor Stack
  S = 0
End Constructor

' Destruktor
'-----------
Destructor Stack
  While S <> 0
    pop
  Wend
End Destructor

' Sprawdza,
' czy stos jest pusty
'--------------------
Function Stack.empty As Integer
  If S = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu
'--------------------
Function Stack.top As Integer
  If S = 0 Then
    top = -MAXINT
  Else
    top = S->v
  End If
End Function

' Zapisuje na stos
'-----------------
Sub Stack.push(ByVal v As Integer)
  Dim e As SLel Ptr
  e = New SLel
  e->v = v
  e->next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub Stack.pop
  Dim e As SLel Ptr
  If S Then
  	 e = S
  	 S = S->Next
  	 Delete e
  End If
End Sub

' Funkcja bada graf pod kątem posiadania
' cyklu lub ścieżki Eulera
' n - liczba wierzchołków w grafie
' graf - tablica list sąsiedztwa
' Wynik:
' 0 - graf nie zawiera ścieżki
'     lub cyklu Eulera
' 1 - graf zawiera ścieżkę Eulera
' 2 - graf zawiera cykl Eulera
'--------------------------------------
Function isEulerian(ByVal n As integer, _
 ByVal graf As SLel Ptr Ptr) _
            As Integer
  Dim As Integer no, nc, i, v, u
  Dim As Stack S
  Dim As Byte Ptr vs
  Dim As SLel Ptr p

  i = 0
  while (i < n) AndAlso _
        (graf[i] = 0)
    ' Szukamy pierwszego
    ' wierzchołka z sąsiadami
    i += 1
  Wend
  ' Graf nie ma krawędzi
  If i = n Then Return 1
  ' Tworzymy dynamicznie
  ' tablicę odwiedzin
  vs = New Byte [n]
  ' Wypełniamy ją wartościami false
  For v = 0 To n-1
    vs[v] = 0
  Next
  ' Zerujemy licznik wierzchołków
  ' o stopniu nieparzystym
  no = 0
  ' Wierzchołek startowy na stos
  S.push(i)
  ' oznaczamy go jako odwiedzony
  vs[i] = 1
  ' Uruchamiamy przejście DFS,
  ' aby wyznaczyć spójną składową
  ' zawierającą wierzchołek startowy
  ' oraz policzyć stopnie wierzchołków
  ' i wyznaczyć liczbę wierzchołków
  ' o stopniach nieparzystych
  While S.empty = 0
    ' Pobieramy do v wierzchołek
    ' ze stosu
    v = S.top
    ' Pobrany wierzchołek
    ' usuwamy ze stosu
    S.pop
    ' Licznik sąsiadów na zero
    nc = 0
    ' Przeglądamy sąsiadów wierzchołka v
    p = graf[v]
    While p <>0
      ' Zwiększamy licznik sąsiadów
      nc += 1
      u = p->v
      ' Szukamy nieodwiedzonych sąsiadów
      If vs[u] = 0 Then
        ' Oznaczamy ich
        ' jako odwiedzonych
        vs[u] = 1
        ' i umieszczamy na stosie
        S.push(u)
      End If
      ' Następny sąsiad na liście
      p = p->next
    Wend
    ' Nieparzysta liczba sąsiadów?
    If nc Mod 2 = 1 Then no += 1
  Wend
  ' Przeglądamy pozostałe
  ' wierzchołki grafu
  For v = i+1 To n-1
    If (vs[v] = 0) AndAlso _
       (graf[v] <> 0) Then
      ' Usuwamy tablicę odwiedzin
      Delete [] vs
      ' graf nie jest spójny
      Return 0
    End If
  Next
  ' Usuwamy tablicę odwiedzin
  Delete [] vs
  ' Graf zawiera cykl Eulera
  If no = 0 Then Return 2
  ' Graf zawiera ścieżkę Eulera
  If no = 2 Then Return 1
  ' Graf nie posiada
  ' ścieżki lub cyklu Eulera
  Return 0
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
Print
Select Case isEulerian(n, A)
  case 0
    Print "NOT AN EULERIAN GRAPH"
  Case 1
    Print "SEMI-EULERIAN GRAPH"
  Case 2
    Print "EULERIAN GRAPH"
End Select
' 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

# Badanie, czy graf zawiera
# cykl lub ścieżkę Eulera
# Data: 30.01.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

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


MAXINT = 2147483647


class Stack:
    # Konstruktor
    def __init__(self):
        self.s = None


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


    # Sprawdza,
    # czy stos jest pusty
    def empty(self):
       return not self.s


    # Zwraca szczyt stosu
    def top(self):
        global MAXINT
        if not self.s:
            return -MAXINT
        else:
            return self.s.v


    # Zapisuje na stos
    def push(self, v):
        e = SLel()
        e.v = v
        e.next = self.s
        self.s = e


    # Usuwa ze stosu
    def pop(self):
        if self.s:
            self.s = self.s.next


# Funkcja bada graf pod kątem
# posiadania cyklu lub ścieżki Eulera
# n - liczba wierzchołków w grafie
# graf - tablica list sąsiedztwa
# Wynik:
# 0 - graf nie zawiera ścieżki
#     lub cyklu Eulera
# 1 - graf zawiera ścieżkę Eulera
# 2 - graf zawiera cykl Eulera
def is_eulerian(n, graf):
    s = Stack()
    i = 0
    while (i < n) and not graf[i]:
        # Szukamy pierwszego
        # wierzchołka z sąsiadami
        i += 1
    # Graf nie ma krawędzi
    if i == n: return 1
    # Tworzymy dynamicznie
    # tablicę odwiedzin
    vs = [False] * n
    # Zerujemy licznik wierzchołków
    # o stopniu nieparzystym
    no = 0
    # Wierzchołek startowy na stos
    s.push(i)
    # oznaczamy go jako odwiedzony
    vs[i] = True
    # Uruchamiamy przejście DFS,
    # aby wyznaczyć spójną składową
    # zawierającą wierzchołek startowy
    # oraz policzyć stopnie
    # wierzchołków i wyznaczyć liczbę
    # wierzchołków o stopniach
    # nieparzystych
    while not s.empty():
        # Pobieramy do v wierzchołek
        # ze stosu
        v = s.top()
        # Pobrany wierzchołek
        # usuwamy ze stosu
        s.pop()
        # Licznik sąsiadów na zero
        nc = 0
        # Przeglądamy sąsiadów
        # wierzchołka v
        p = graf[v]
        while p:
            # Zwiększamy licznik
            # sąsiadów
            nc += 1
            u = p.v
            # Szukamy nieodwiedzonych
            # sąsiadów
            if not vs[u]:
                # Oznaczamy ich
                # jako odwiedzonych
                vs[u] = True
                # i umieszczamy
                # na stosie
                s.push(u)
            # Następny sąsiad
            # na liście
            p = p.next
        # Nieparzysta
        # liczba sąsiadów?
        if nc % 2: no += 1
    # Przeglądamy pozostałe
    # wierzchołki grafu
    for v in range(i+1,n):
        if not vs[v] and graf[v]:
            # Usuwamy
            # tablicę odwiedzin
            del vs
            # graf nie jest spójny
            return 0
    # Usuwamy tablicę odwiedzin
    del vs
    # Graf zawiera cykl Eulera
    if not no: return 2
    # Graf zawiera ścieżkę Eulera
    if no == 2: return 1
    # Graf nie posiada
    # ścieżki lub cyklu Eulera
    return 0


# **********************
# *** 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
print()
match is_eulerian(n, a):
    case 0:
        print("NOT AN EULERIAN GRAPH")
    case 1:
        print("SEMI-EULERIAN GRAPH")
    case 2:
        print("EULERIAN GRAPH")
# Usuwamy tablicę list sąsiedztwa
for i in range(n):
    while a[i]:
        a[i] = a[i].next
del a

// Badanie istnienia
// cyklu lub ścieżki Eulera
// Data: 3.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program scc;

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

TList = array of PSLel;

// Definicja typu obiektowego Stack
//---------------------------------
Stack = object
  private
    // lista przechowująca stos
    S : PSLel;

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

// Zmienne globalne
//-----------------
var
  n,m,cvn : integer;
  VN,VLow,Vind,Voutd,C : array of integer;
  VS : array of boolean;
  S : Stack;
  graf : array of PSLel;

//---------------------
// Metody obiektu Stack
//---------------------

// Konstruktor
//------------
constructor Stack.init;
begin
  S := nil;
end;

// Destruktor
//-----------
destructor Stack.destroy;
begin
  while S <> nil do pop;
end;

// Sprawdza, czy stos jest pusty
//------------------------------
function Stack.empty : boolean;
begin
  if S = nil then
    empty := true
  else
    empty := false;
end;

// Zwraca liczbę ze szczytu stosu
//----------------------------------
function Stack.top : integer;
begin
  if S = nil then
    top := -MAXINT
  else
    top := S^.v;
end;

// Umieszcza dane na stosie
//-------------------------
procedure Stack.push(v : integer);
var
  e : PSLel;

begin
  new(e);
  e^.v := v;
  e^.next := S;
  S := e;
end;

// Usuwa dane ze stosu
//--------------------
procedure Stack.pop;
var
  e : PSLel;
begin
  if S <> nil then
  begin
    e := S;
    S := S^.next;
    dispose(e);
  end;
end;

// Zwraca mniejszą z dwóch liczb
//------------------------------
function min(a, b : integer)
                  : integer;
begin
  if a < b then
    min := a
  else
    min := b;
end;

// Procedura wykonująca przejście DFS
// i wyznaczająca silnie spójną
// składową oraz stopnie wierzchołków
// v - wierzchołek startowy dla DFS
//-----------------------------------
procedure DFSscc(v : integer);
var
  u : integer;
  p : PSLel;
begin
  // Zwiększamy numer wierzchołka
  inc(cvn);
  // Numerujemy bieżący wierzchołek
  VN[v] := cvn;
  // Ustalamy wstępnie parametr Low
  VLow[v] := cvn;
  // Wierzchołek na stos
  S.push(v);
  // Zapamiętujemy,
  // że v jest na stosie
  VS[v] := true;
  // Przeglądamy listę sąsiadów
  p := graf[v];
  while p <> nil do
  begin
    // Wyznaczamy stopień wychodzący
    inc(Voutd[v]);
    // i wchodzący
    inc(Vind[p^.v]);
    // Jeśli sąsiad jest nieodwiedzony, to
    if VN[p^.v] = 0 then
    begin
      // wywołujemy dla niego
      // rekurencyjnie DFS
      DFSscc(p^.v);
      // i obliczamy parametr Low dla v
      VLow[v] := min(VLow[v],VLow[p^.v]);
    end
    // jeśli sąsiad odwiedzony,
    // lecz wciąż na stosie,
    else if VS[p^.v] then
      // to wyznaczamy parametr Low dla v
    VLow[v] := min(VLow[v],VN[p^.v]);
    p := p^.next;
  end;
  // Sprawdzamy,
  //  czy mamy kompletną składową
  if VLow[v] = VN[v] then
  begin
    repeat
      // Pobieramy wierzchołek ze stosu
      u := S.top;
      // Pobrany wierzchołek
      // usuwamy ze stosu
      S.pop;
      // Zapamiętujemy,
      // że nie ma go już na stosie
      VS[u] := false;
      // Zapamiętujemy numer
      // silnie spójnej składowej
      C[u] := v;
    // Kontynuujemy
    // aż do korzenia składowej
    until u = v;
  end;
end;

// Funkcja bada istnienie
// cyklu lub ścieżki Eulera
// Zwraca:
// 0 - brak cyklu i ścieżki
// 1 - jest ścieżka Eulera
// 2 - jest cykl Eulera
//-------------------------
function isEulerian : integer;
var
  v, cinout, coutin : integer;
begin
  // Zerujemy numer wierzchołka
  cvn := 0;
  // Przeglądamy kolejne wierzchołki
  for v := 0 to n-1 do
    // W wierzchołku nieodwiedzonym
    // uruchamiamy DFS
    if VN[v] = 0 then DFSscc(v);
  // Szukamy pierwszego
  // wierzchołka o niezerowym stopniu
  v := 0;
  while (v < n) and
        (Vind[v]+Voutd[v] = 0) do
    inc(v);
  // Graf jest pusty
  if v = n then Exit(0);
  // Zapamiętujemy numer
  // silnie spójnej składowej
  cvn := C[v];
  // Licznik wierzchołków
  // o większym o 1 stopniu wchodzącym
  cinout := 0;
  // Licznik wierzchołków
  // o większym o 1 stopniu wychodzącym
  coutin := 0;
  // Przeglądamy graf
  while v < n do
  begin
    if Vind[v]+Voutd[v] > 0 then
    begin
      // Graf nie jest silnie spójny
      if C[v] <> cvn then Exit(0);
      if Vind[v] <> Voutd[v] then
      begin
        if Vind[v]-Voutd[v] = 1 then
        begin
          inc(cinout);
          // Za dużo wierzchołków
          // o nierównych stopniach
          if cinout > 1 then Exit(0);
        end
        else if Voutd[v]-Vind[v] = 1 then
        begin
          inc(coutin);
          // Za dużo wierzchołków
          // o nierównych stopniach
          if coutin > 1 then Exit(0);
        end
        // Stopnie różnią się
        // o więcej niż 1
        else Exit(0);
      end;
    end;
    inc(v);
  end;
  // Analizujemy stan liczników
  if cinout = 1 then
    // Mamy ścieżkę Eulera
    Exit(1)
  else
    // Mamy cykl Eulera
    Exit(2);
end;

// **********************
// *** Program główny ***
// **********************

var
  i, v, u : integer;
  p, r : PSLel;

begin
  // Tworzymy pusty stos
  S.init;
  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablice dynamiczne
  SetLength(graf, n);
  SetLength(VN, n);
  SetLength(VS, n);
  SetLength(VLow, n);
  SetLength(Vind, n);
  SetLength(Voutd, n);
  SetLength(C, n);
  // Inicjujemy tablice
  for i := 0 to n-1 do
  begin
    graf[i] := nil;
    VN[i] := 0;
    Vind[i] := 0;
    Voutd[i] := 0;
    VS[i] := false;
  end;
  // Odczytujemy kolejne
  // definicje krawędzi.
  for i := 0 to m-1 do
  begin
    // Wierzchołki tworzące krawędź
    read(v, u);
    // Tworzymy nowy element
    new(p);
    // Numerujemy go jako u
    p^.v := u;
    // i dodajemy na początek
    // listy graf[v]
    p^.next := graf[v];
    graf[v] := p;
  end;
  writeln;
  // Badamy graf
  case isEulerian of
    0: writeln('NOT AN EULERIAN GRAPH');
    1: writeln('SEMI-EULERIAN GRAPH');
    2: writeln('EULERIAN GRAPH');
  end;
  // Usuwamy zmienne dynamiczne
  for i := 0 to n-1 do
  begin
    p := graf[i];
    while p <> nil do
    begin
      r := p;
      p := p^.next;
      dispose(r);
    end;
  end;
  SetLength(graf, 0);
  SetLength(VN, 0);
  SetLength(VLow, 0);
  SetLength(VS, 0);
  SetLength(Vind, 0);
  SetLength(Voutd, 0);
  SetLength(C, 0);
  S.destroy;
end.

// Badanie istnienia
// cyklu lub ścieżki Eulera
// Data: 3.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

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

// Definicja typu
// obiektowego Stack
//------------------
class Stack
{
  private:
    // lista przechowująca stos
    SLel * S;

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

// Zmienne globalne
//-----------------
const int MAXINT = 2147483647;
int n,m,cvn;
int *VN,*VLow,*Vind,*Voutd,*C;
bool *VS;
Stack S;
SLel **graf;

//---------------------
// Metody obiektu Stack
//---------------------

// Konstruktor
//------------
Stack::Stack()
{
  S = nullptr;
}

// Destruktor
//-----------
Stack::~Stack()
{
  while(S) pop();
}

// Sprawdza, czy stos jest pusty
//------------------------------
bool Stack::empty(void)
{
  return !S;
}

// Zwraca szczyt stosu
//--------------------
int Stack::top (void)
{
  if(S)
    return S->v;
  else
    return -MAXINT;
}

// Zapisuje na stos
//-----------------
void Stack::push(int v)
{
  SLel * e = new SLel;
  e->v = v;
  e->next = S;
  S = e;
}

// Usuwa ze stosu
//---------------
void Stack::pop(void)
{
  if(S)
  {
    SLel * e = S;
    S = S->next;
    delete e;
  }
}

// Procedura wykonująca
// przejście DFS i wyznaczająca
// silnie spójną składową
// oraz stopnie wierzchołków
// v - wierzchołek startowy dla DFS
//---------------------------------
void DFSscc(int v)
{
  int u;
  SLel * p;

  // Ustalamy wstępnie parametr Low
  VN[v] = VLow[v] = ++cvn;
  // Wierzchołek na stos
  S.push(v);
  // Zapamiętujemy,
  // że v jest na stosie
  VS[v] = true;
  // Przeglądamy listę sąsiadów
  for(p = graf[v];p;p = p->next)
  {
    // Wyznaczamy stopień wychodzący
    ++Voutd[v];
    // i wchodzący
    ++Vind[p->v];
    // Jeśli sąsiad
    // jest nieodwiedzony, to
    if(!VN[p->v])
    {
      // wywołujemy dla niego
      // rekurencyjnie DFS
      DFSscc(p->v);
      // i obliczamy parametr Low dla v
      VLow[v] = min(VLow[v],VLow[p->v]);
    }
     // jeśli sąsiad odwiedzony,
     // lecz wciąż na stosie,
     else if(VS[p->v])
       // to wyznaczamy parametr Low dla v
       VLow[v] = min(VLow[v],VN[p->v]);
  }
  // Sprawdzamy,
  // czy mamy kompletną składową
  if(VLow[v] == VN[v])
    do
    {
      // Pobieramy wierzchołek
      // ze stosu
      u = S.top();
      // Pobrany wierzchołek
      // usuwamy ze stosu
      S.pop();
      // Zapamiętujemy,
      // że nie ma go już na stosie
      VS[u] = false;
      // Zapamiętujemy numer
      // silnie spójnej składowej
      C[u] = v;
    // Kontynuujemy
    // aż do korzenia składowej
    } while(u != v);
}

// Funkcja bada istnienie
// cyklu lub ścieżki Eulera
// Zwraca:
// 0 - brak cyklu i ścieżki
// 1 - jest ścieżka Eulera
// 2 - jest cykl Eulera
//-------------------------
int isEulerian()
{
  int v, cinout, coutin;

  // Zerujemy numer wierzchołka
  cvn = 0;
  // Przeglądamy kolejne wierzchołki
  for(v = 0; v < n; v++)
    // W wierzchołku nieodwiedzonym
    // uruchamiamy DFS
    if(!VN[v]) DFSscc(v);
  // Szukamy pierwszego wierzchołka
  // o niezerowym stopniu
  for(v = 0; (v < n) &&
             !(Vind[v] = Voutd[v]);
             v++);
  // Graf jest pusty
  if(v == n) return 0;
  // Zapamiętujemy
  // numer silnie spójnej składowej
  cvn = C[v];
  // Zerujemy liczniki
  cinout = coutin = 0;
  // Przeglądamy graf
  for(;v < n;v++)
    if(Vind[v] +

 Voutd[v])
    {
      // graf nie jest silnie spójny
      if(C[v] != cvn) return 0;
      if(Vind[v] != Voutd[v])
      {
        if(Vind[v]-Voutd[v] == 1)
        {
          // Za dużo wierzchołków
          // o nierównych stopniach
          if(++cinout > 1) return 0;
        }
        else if(Voutd[v]-Vind[v] == 1)
        {
          // Za dużo wierzchołków
          // o nierównych stopniach
          if(++coutin > 1) return 0;
        }
        // Stopnie różnią się
        // o więcej niż 1
        else return 0;
      }
    }
  // Analizujemy stan liczników
  //---------------------------
  // Mamy ścieżkę Eulera
  if(cinout == 1) return 1;
  // Mamy cykl Eulera
  else return 2;
}

// **********************
// *** Program główny ***
// **********************

int main()
{
  int i, v, u;
  SLel *p, *r;

  // Odczytujemy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablice dynamiczne
  graf = new SLel * [n];
  VN = new int [n];
  VS = new bool [n];
  VLow = new int [n];
  Vind = new int [n];
  Voutd = new int [n];
  C = new int [n];
  // Inicjujemy tablice
  for(i = 0; i < n; i++)
  {
    graf[i] = nullptr;
    VN[i] = Vind[i] = Voutd[i] = 0;
    VS[i] = false;
  }
  // Odczytujemy kolejne
  // definicje krawędzi.
  for(i = 0; i < m; i++)
  {
    // Wierzchołki tworzące krawędź
    cin >> v >> u;
    // Tworzymy nowy element
    p = new SLel;
    // Numerujemy go jako u
    p->v = u;
    // i dodajemy na początek
    // listy graf[v]
    p->next = graf[v];
    graf[v] = p;
  }
  cout << endl;
  // Badamy graf
  switch(isEulerian())
  {
    case 0:
      cout << "NOT AN EULERIAN GRAPH\n";
      break;
    case 1:
      cout << "SEMI-EULERIAN GRAPH\n";
      break;
    case 2:
      cout << "EULERIAN GRAPH\n";
      break;
  }
  // Usuwamy zmienne dynamiczne
  for(i = 0; i < n; i++)
  {
    p = graf[i];
    while(p)
    {
      r = p;
      p = p->next;
      delete r;
    }
  }
  delete [] graf;
  delete [] VN;
  delete [] VLow;
  delete [] VS;
  delete [] Vind;
  delete [] Voutd;
  delete [] C;
  return 0;
}

' Badanie istnienia
' cyklu lub ścieżki Eulera
' Data: 3.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

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

Type Stack
  Private:
    ' lista zawierająca stos
    S As SLel Ptr
  Public:
    Declare Constructor
    Declare Destructor
    Declare Function empty As Integer
    Declare Function top As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop
End Type

' Zmienne globalne
'-----------------
Const MAXINT = 2147483647
Dim Shared As Integer n, m, cvn
Dim Shared As Integer Ptr VN, VLow, _
                          Vind, Voutd, C
Dim Shared As Byte Ptr VS
Dim Shared As Stack S
Dim Shared As SLel Ptr Ptr graf

'---------------------
' Metody obiektu Stack
'---------------------

' Konstruktor
'------------
Constructor Stack
  S = 0
End Constructor

' Destruktor
'-----------
Destructor Stack
  While S <> 0
    pop
  Wend
End Destructor

' Sprawdza, czy stos jest pusty
'------------------------------
Function Stack.empty As Integer
  If S = 0 Then Return 1
  Return 0
End Function

' Zwraca szczyt stosu
'--------------------
Function Stack.top As Integer
  If S <> 0 Then
    top = S->v
  Else
    top = -MAXINT
  End If
End Function

' Zapisuje na stos
'-----------------
Sub Stack.push(ByVal v As Integer)
  Dim e As SLel Ptr
  e = New SLel
  e->v = v
  e->next = S
  S = e
End Sub

' Usuwa ze stosu
'---------------
Sub Stack.pop
  Dim e As SLel Ptr
  If S <> 0 Then
    e = S
    S = S->Next
    Delete e
  End If
End Sub

' Funkcja zwraca
' mniejszą z liczb a i b
'-----------------------
Function min(ByVal a As Integer, _
             ByVal b As Integer) _
                     As Integer
  If a < b Then
    Return a
  Else
    Return b
  EndIf
End Function

' Procedura wykonująca
' przejście DFS i wyznaczająca
' silnie spójną składową
' oraz stopnie wierzchołków
' v - wierzchołek startowy dla DFS
'---------------------------------
sub DFSscc(ByVal v As Integer)

  Dim As Integer u
  Dim As SLel Ptr p

  cvn += 1
  VN[v] = cvn
  ' Ustalamy wstępnie parametr Low
  VLow[v] = cvn
  ' Wierzchołek na stos
  S.push(v)
  ' Zapamiętujemy,
  ' że v jest na stosie
  VS[v] = 1
  p = graf[v]
  ' Przeglądamy listę sąsiadów
  While p <> 0
    ' Wyznaczamy stopień wychodzący
    Voutd[v] += 1
    ' i wchodzący
    Vind[p->v] += 1
    ' Jeśli sąsiad jest
    ' nieodwiedzony, to
    If VN[p->v] = 0 Then
      ' wywołujemy dla niego
      ' rekurencyjnie DFS
      DFSscc(p->v)
      ' i obliczamy parametr Low dla v
      VLow[v] = min(VLow[v],VLow[p->v])
    ' Jeśli sąsiad odwiedzony,
    ' lecz wciąż na stosie,
    ElseIf VS[p->v] = 1 Then
      ' to wyznaczamy parametr
      ' Low dla v
      VLow[v] = min(VLow[v],VN[p->v])
    End If
    p = p->next
  Wend
  ' Sprawdzamy,
  ' czy mamy kompletną składową
  If VLow[v] = VN[v] Then
    Do
      ' Pobieramy wierzchołek ze stosu
      u = S.top
      ' Pobrany wierzchołek
      ' usuwamy ze stosu
      S.pop
      ' Zapamiętujemy,
      ' że nie ma go już na stosie
      VS[u] = 0
      ' Zapamiętujemy numer
      ' silnie spójnej składowej
      C[u] = v
    ' Kontynuujemy
    ' aż do korzenia składowej
    Loop While u <> v
  End If
End Sub

' Funkcja bada istnienie
' cyklu lub ścieżki Eulera
' Zwraca:
' 0 - brak cyklu i ścieżki
' 1 - jest ścieżka Eulera
' 2 - jest cykl Eulera
'-------------------------
Function isEulerian As Integer
  Dim As Integer v, cinout, coutin

  ' Zerujemy numer wierzchołka
  cvn = 0
  ' Przeglądamy kolejne wierzchołki
  For v = 0 To n-1
    ' W wierzchołku nieodwiedzonym
    ' uruchamiamy DFS
    If VN[v] = 0 then DFSscc(v)
  Next
   ' Szukamy pierwszego wierzchołka
   ' o niezerowym stopniu
  v = 0
  While (v < n) AndAlso _
        (Vind[v]+Voutd[v] = 0)
    v += 1
  Wend
  ' Graf jest pusty
  If v = n then Return 0
  ' Zapamiętujemy numer
  ' silnie spójnej składowej
  cvn = C[v]
  ' Zerujemy liczniki
  cinout = 0
  coutin = 0
  ' Przeglądamy graf
  While v < n
    If Vind[v] = Voutd[v] > 0 Then
      ' graf nie jest silnie spójny
      If C[v] <> cvn Then Return 0
      If Vind[v] <> Voutd[v] Then
        If Vind[v]-Voutd[v] = 1 Then
          cinout += 1
          ' Za dużo wierzchołków
          ' o nierównych stopniach
          If cinout > 1 then return 0
        ElseIf Voutd[v]-Vind[v] = 1 Then
          coutin += 1
          ' Za dużo wierzchołków
          ' o nierównych stopniach
          If coutin > 1 Then Return 0
        Else
          ' Stopnie różnią się
          ' o więcej niż 1
          Return 0
        End If
      End If
    End If
    v += 1
  Wend
  ' Analizujemy stan liczników
  '---------------------------
  ' Mamy ścieżkę Eulera
  If cinout = 1 Then Return 1
  ' mamy cykl Eulera
  return 2
End Function

' **********************
' *** Program główny ***
' **********************

Dim As Integer i, v, u
Dim As SLel Ptr p, r

Open Cons For Input As #1
' Odczytujemy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablice dynamiczne
graf = New SLel Ptr [n]
VN = New Integer [n]
VS = New Byte [n]
VLow = New Integer [n]
Vind = New Integer [n]
Voutd = New Integer [n]
C = New Integer [n]
' Inicjujemy tablice
For i = 0 To n-1
  graf[i]  = 0
  VN[i]    = 0
  Vind[i]  = 0
  Voutd[i] = 0
  VS[i]    = 0
Next
' Odczytujemy kolejne
' definicje krawędzi.
For i = 1 To m
  ' Wierzchołki tworzące krawędź
  Input #1, v, u
  ' Tworzymy nowy element
  p = New SLel
  ' Numerujemy go jako w
  p->v = u
  ' Dodajemy go
  ' na początek listy graf[v]
  p->next = graf[v]
  graf[v] = p
Next
Close #1
Print
' Badamy graf
Select Case isEulerian
  Case 0
    Print "NOT AN EULERIAN GRAPH"
  Case 1
    Print "SEMI-EULERIAN GRAPH"
  Case 2
    Print "EULERIAN GRAPH"
End Select
' Usuwamy tablice dynamiczne
For i = 0 To n-1
  p = graf[i]
  While p <> 0
    r = p
    p = p->next
    Delete r
  Wend
Next
Delete [] graf
Delete [] VN
Delete [] VLow
Delete [] VS
Delete [] Vind
Delete [] Voutd
Delete [] C
End

# Badanie istnienia
# cyklu lub ścieżki Eulera
# Data: 3.02.2014
# (C)2014 mgr Jerzy Wałaszek
#---------------------------

# Klasy dla dynamicznej
# tablicy list sąsiedztwa
# oraz stosu
class SLel:
    def __init__(self):
        self.next = None
        self.v = 0

MAXINT = 2147483647

class Stack:
    # Konstruktor
    def __init__(self):
        self.s = None


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


    # Sprawdza,
    # czy stos jest pusty
    def empty(self):
        return not self.s


    # Zwraca szczyt stosu
    def top(self):
        global MAXINT
        if self.s:
            return self.s.v
        else:
            return -MAXINT


    # Zapisuje na stos
    def push(self, v):
        e = SLel()
        e.v = v
        e.next = self.s
        self.s = e


    # Usuwa ze stosu
    def pop(self):
        if self.s:
            self.s = self.s.next


# Procedura wykonująca
# przejście DFS i wyznaczająca
# silnie spójną składową
# oraz stopnie wierzchołków
# v - wierzchołek startowy dla DFS
def dfs_scc(v):
    global cvn,vn,vlow,s,vs,graf
    global voutd,vind,c
    cvn += 1
    vn[v] = cvn
    # Ustalamy wstępnie parametr Low
    vlow[v] = cvn
    # Wierzchołek na stos
    s.push(v)
    # Zapamiętujemy,
    # że v jest na stosie
    vs[v] = True
    p = graf[v]
    # Przeglądamy listę sąsiadów
    while p:
        # Wyznaczamy stopień wychodzący
        voutd[v] += 1
        # i wchodzący
        vind[p.v] += 1
        # Jeśli sąsiad jest
        # nieodwiedzony, to
        if not vn[p.v]:
            # wywołujemy dla niego
            # rekurencyjnie DFS
            dfs_scc(p.v)
            # i obliczamy parametr Low dla v
            vlow[v] = min(vlow[v],vlow[p.v])
        # Jeśli sąsiad odwiedzony,
        # lecz wciąż na stosie,
        elif vs[p.v]:
            # to wyznaczamy parametr
            # Low dla v
            vlow[v] = min(vlow[v],vn[p.v])
        p = p.next
    # Sprawdzamy,
    # czy mamy kompletną składową
    if vlow[v] == vn[v]:
        while True:
            # Pobieramy wierzchołek ze stosu
            u = s.top()
            # Pobrany wierzchołek
            # usuwamy ze stosu
            s.pop()
            # Zapamiętujemy,
            # że nie ma go już na stosie
            vs[u] = False
            # Zapamiętujemy numer
            # silnie spójnej składowej
            c[u] = v
            # Kontynuujemy
            # aż do korzenia składowej
            if u == v: break


# Funkcja bada istnienie
# cyklu lub ścieżki Eulera
# Zwraca:
# 0 - brak cyklu i ścieżki
# 1 - jest ścieżka Eulera
# 2 - jest cykl Eulera
def is_eulerian():
    global cvn,n,vn,vind,voutd,c
    # Zerujemy numer wierzchołka
    cvn = 0
    # Przeglądamy kolejne wierzchołki
    for v in range(n):
        # W wierzchołku nieodwiedzonym
        # uruchamiamy DFS
        if not vn[v]: dfs_scc(v)
     # Szukamy pierwszego wierzchołka
     # o niezerowym stopniu
    v = 0
    while (v < n) and \
          (vind[v]+voutd[v] == 0):
        v += 1
    # Graf jest pusty
    if v == n: return 0
    # Zapamiętujemy numer
    # silnie spójnej składowej
    cvn = c[v]
    # Zerujemy liczniki
    cinout = 0
    coutin = 0
    # Przeglądamy graf
    while v < n:
        if vind[v]+voutd[v] > 0:
            # graf nie jest silnie spójny
            if c[v] != cvn: return 0
            if vind[v] != voutd[v]:
                if vind[v]-voutd[v] == 1:
                    cinout += 1
                    # Za dużo wierzchołków
                    # o nierównych stopniach
                    if cinout > 1: return 0
                elif voutd[v]-vind[v] == 1:
                    coutin += 1
                    # Za dużo wierzchołków
                    # o nierównych stopniach
                    if coutin > 1: return 0
                else:
                    # Stopnie różnią się
                    # o więcej niż 1
                    return 0
        v += 1
    # Analizujemy stan liczników
    #---------------------------
    # Mamy ścieżkę Eulera
    if cinout == 1: return 1
    # mamy cykl Eulera
    return 2


# **********************
# *** Program główny ***
# **********************

cvn = 0
s = Stack()
# Odczytujemy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablice dynamiczne
graf = [None] * n
vn = [0] * n
vs = [False] * n
vlow = [0] * n
vind = [0] * n
voutd = [0] * n
c = [0] * n
# Odczytujemy kolejne
# definicje krawędzi.
for i in range(m):
    # Wierzchołki tworzące krawędź
    x = input().split()
    v = int(x[0])
    u = int(x[1])
    # Tworzymy nowy element
    p = SLel()
    # Numerujemy go jako w
    p.v = u
    # Dodajemy go na początek listy graf[v]
    p.next = graf[v]
    graf[v] = p
print()
# Badamy graf
match is_eulerian():
    case 0:
        print("NOT AN EULERIAN GRAPH")
    case 1:
        print("SEMI-EULERIAN GRAPH")
    case 2:
        print("EULERIAN GRAPH")
# Usuwamy tablice dynamiczne
for i in range(n):
    while graf[i]:
        graf[i] = graf[i].next
del graf,vn,vlow,vs,vind,voutd,c