// Wyszukiwanie cyklu Eulera
// Data: 19.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program EulerCycle;

// Typy dla dynamicznej
// macierzy sąsiedztwa
type
  // Wiersz
  nptr = array of integer;

// Zmienne globalne
var
  n, m, sptr : integer;
  // Macierz sąsiedztwa
  A : array of nptr;
  // Stos w tablicy
  S : array of integer;

// Procedura wyszukuje
// cykl Eulera
// We:
// v - wierzchołek startowy
//-------------------------
procedure DFSEuler(v : integer);
var
  i : integer;
begin
  // Przeglądamy sąsiadów
  for i := 0 to n-1 do
    while A[v][i] > 0 do
    begin
      // Usuwamy krawędź
      dec(A[v][i]);
      dec (A[i][v]);
      // Rekurencja
      DFSEuler(i);
    end;
  // Wierzchołek v
  // umieszczamy na stosie
  S[sptr] := v;
  inc(sptr);
end;

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

var
  i, j, v1, v2 : integer;
begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę wskaźników
  SetLength(A, n);
  // Tworzymy stos
  SetLength(S, m+1);
  sptr := 0;
  for i := 0 to n-1 do
    // Tworzymy wiersze
    // macierzy sąsiedztwa
    SetLength(A[i], n);
  // Macierz wypełniamy zerami
  for i := 0 to n-1 do
    for j := 0 to n-1 do
      A[i][j] := 0;
  // Odczytujemy kolejne
  // definicje krawędzi
  for i := 1 to m do
  begin
    // wierzchołki końcowe
    // krawędzi
    read(v1, v2);
    // Krawędź v1->v2 obecna
    inc(A[v1][v2]);
    // Krawędź v2->v1 obecna
    inc(A[v2][v1]);
  end;
  writeln;
  // Wyznaczamy cykl Eulera
  DFSEuler(0);
  // Wypisujemy zawartość stosu
  write ('EULERIAN CYCLE : ');
  for i := 0 to sptr-1 do
    write(S[i], ' ');
  writeln;
  // Usuwamy tablice dynamiczne
  for i := 0 to n-1 do
    SetLength(A[i], 0);
  SetLength(A, 0);
  SetLength(S, 0);
end.

// Wyszukiwanie cyklu Eulera
// Data: 19.03.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// Zmienne globalne

int n, m, sptr;
// Macierz sąsiedztwa
int ** A;
// Stos w tablicy
int * S;

// Procedura wyszukuje
// cykl Eulera
// We:
// v - wierzchołek startowy
//-------------------------
void DFSEuler(int v)
{
  int i;

  // Przeglądamy sąsiadów
  for(i = 0; i < n; i++)
    while(A[v][i])
    {
      // Usuwamy krawędź
      A[v][i]--;
      A[i][v]--;
      // Rekurencja
      DFSEuler(i);
    }
  // Wierzchołek v
  // umieszczamy na stosie
  S[sptr++] = v;
}

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

int main()
{
  int i, j, v1, v2;

  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy tablicę
  // wskaźników
  A = new int * [n];
  // Tworzymy stos
  S = new int [m+1];
  sptr = 0;
  for(i = 0; i < n; i++)
    // Tworzymy wiersze
    // macierzy sąsiedztwa
    A[i] = new int [n];
  // Macierz wypełniamy zerami
  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
      A[i][j] = 0;
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // wierzchołki końcowe
    // krawędzi
    cin >> v1 >> v2;
    // Krawędź v1->v2 obecna
    A[v1][v2]++;
    // Krawędź v2->v1 obecna
    A[v2][v1]++;
  }
  cout << endl;
  // Wyznaczamy cykl Eulera
  DFSEuler(0);
  // Wypisujemy
  // zawartość stosu
  cout << "EULERIAN CYCLE : ";
  for(i = 0; i < sptr; i++)
    cout << S[i] << " ";
  cout << endl;
  // Usuwamy
  // tablice dynamiczne
  for(i = 0; i < n; i++)
    delete [] A[i];
  delete [] A;
  delete [] S;
  return 0;
}

' Wyszukiwanie cyklu Eulera
' Data: 19.03.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Zmienne globalne

Dim Shared As Integer n, m, sptr
' Macierz sąsiedztwa
Dim Shared As Integer Ptr Ptr A
' Stos w tablicy
Dim Shared As Integer Ptr S

' Procedura wyszukuje cykl Eulera
' We:
' v - wierzchołek startowy
'--------------------------------
Sub DFSEuler(ByVal v As Integer)
 
  Dim As Integer i

  ' Przeglądamy sąsiadów
  For i = 0 To n-1
    While A[v][i]
      ' Usuwamy krawędź
      A[v][i] -= 1
      A[i][v] -= 1
      ' Rekurencja
      DFSEuler(i)
    Wend
  Next
  ' Wierzchołek v umieszczamy
  ' na stosie
  S[sptr] = v
  sptr += 1
End Sub

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

Dim As integer i, j, v1, v2

Open Cons For Input As #1
' Czytamy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę wskaźników
A = New integer Ptr [n]
' Tworzymy stos
S = New Integer [m+1]
sptr = 0
For i = 0 To n-1
  ' Tworzymy wiersze
  ' macierzy sąsiedztwa
  A[i] = New Integer [n]
Next
' Macierz wypełniamy zerami
For i = 0 To n-1
  For j = 0 To n-1
  	 A[i][j] = 0
  Next
Next
' Odczytujemy kolejne
' definicje krawędzi
For i = 0 To m-1
  ' wierzchołki końcowe
  ' krawędzi
  Input #1, v1, v2
  ' Krawędź v1->v2 obecna
  A[v1][v2] += 1
  ' Krawędź v2->v1 obecna
  A[v2][v1] += 1
Next
Print
Close #1
' Wyznaczamy
' cykl Eulera
DFSEuler(0)
' Wypisujemy
' zawartość stosu
Print "EULERIAN CYCLE :";
For i = 0 To sptr-1
  Print S[i];
Next
Print
' Usuwamy
' tablice dynamiczne
For i = 0 To n-1
  Delete [] A[i]
Next
Delete [] A
Delete [] S
End

# Wyszukiwanie cyklu Eulera
# Data: 5.02.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Procedura wyszukuje cykl Eulera
# We:
# v - wierzchołek startowy
#--------------------------------
def dfs_euler(v):
    global a,n,s,sptr
    # Przeglądamy sąsiadów
    for i in range(n):
        while a[v][i]:
            # Usuwamy krawędź
            a[v][i] -= 1
            a[i][v] -= 1
            # Rekurencja
            dfs_euler(i)
    # Wierzchołek v umieszczamy
    # na stosie
    s[sptr] = v
    sptr += 1


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

# Czytamy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę wskaźników
a = [None] * n
# Tworzymy stos
s = [0] * (m+1)
sptr = 0
for i in range(n):
    # Tworzymy wiersze
    # macierzy sąsiedztwa
    a[i] = [0] * n
# Odczytujemy kolejne
# definicje krawędzi
for i in range(m):
    # wierzchołki końcowe
    # krawędzi
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    # Krawędź v1->v2 obecna
    a[v1][v2] += 1
    # Krawędź v2->v1 obecna
    a[v2][v1] += 1
print()
# Wyznaczamy
# cykl Eulera
dfs_euler(0)
# Wypisujemy
# zawartość stosu
print("EULERIAN CYCLE :",end=" ")
for i in range(sptr):
    print(s[i], end=" ")
print()
# Usuwamy
del a,s

// Wyszukiwanie cyklu lub
// ścieżki Eulera
// Algorytm Fleury'ego
// Data: 8.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program fleury;

// Typy dla dynamicznej macierzy
type
  // Wiersz
  nptr = array of byte;

// Zmienne globalne
var
  n, m, cv, sptr : integer;
  // Macierz sąsiedztwa
  A : array of nptr;
  // Stos w tablicy
  S : array of integer;
  // Tablica numerów wierzchołków
  D : array of integer;

// Funkcja wyszukująca
// mosty w grafie
// We:
// v - numer wierzchołka startowego
// vf - ojciec wierzchołka v na
//      drzewie rozpinającym
// Wy:
// Parametr Low dla wierzchołka v
//---------------------------------
function DFSb(v, vf : integer)
                    : integer;
var
  Low, temp, i : integer;
begin
  // Numerujemy wierzchołek
  D[v] := cv;
  // Wstępna wartość Low
  Low := cv;
  // Numer dla następnego
  // wierzchołka
  inc(cv);
  // Przeglądamy sąsiadów v
  for i := 0 to n-1 do
    if (A[v][i] > 0) and
       (i <> vf) then
    begin
      // Jeśli sąsiad
      // nieodwiedzony, to
      if D[i] = 0 then
      begin
        // to wywołujemy
        // rekurencyjnie DFSb()
        temp := DFSb(i, v);
        // Modyfikujemy Low
        if temp < Low then
          Low := temp;
      end
      else
        if D[i] < Low then
          Low := D[i];
    end;
  // Mamy most?
  if (vf > -1) and
     (Low = D[v]) then
  begin
    // Oznaczamy krawędź
    // vf-v jako most
    A[vf][v] := 2;
    A[v][vf] := 2;
  end;
  DFSb := Low;
end;

// Procedura wyszukuje
// cykl lub ścieżkę Eulera
// We:
// v - wierzchołek startowy
//-------------------------
procedure findEuler(v : integer);
var
  u, w, i : integer;
begin
  // W pętli przetwarzamy graf
  while true do
  begin
    // v umieszczamy na stosie
    S[sptr] := v;
    inc(sptr);
    // Szukamy pierwszego
    // sąsiada v
    u := 0;
    while (u < n) and
          (A[v][u] = 0) do
      inc(u);
    // Nie ma sąsiadów,
    // kończymy
    if u = n then break;
    // Zerujemy tablicę D
    for i := 0 to n-1 do
      D[i] := 0;
    // Numer pierwszego
    // wierzchołka dla DFS
    cv := 1;
    // Identyfikujemy
    // krawędzie-mosty
    DFSb(v, -1);
    // Szukamy krawędzi
    // nie będącej mostem
    w := u+1;
    while (A[v][u] = 2) and
          (w < n) do
    begin
      if A[v][w] > 0 then
        u := w;
      inc(w);
    end;
    // Usuwamy krawędź v-u
    A[v][u] := 0;
    A[u][v] := 0;
    // Przechodzimy do u
    v := u;
  end;
end;

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

var
  i, j, v1, v2 : integer;
  // Stopnie wierzchołków
  VD : array of integer;
begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablicę
  // wskaźników
  SetLength(A, n);
  for i := 0 to n-1 do
    // Tworzymy wiersze
    // macierzy sąsiedztwa
    SetLength(A[i], n);
  // Macierz wypełniamy zerami
  for i := 0 to n-1 do
    for j := 0 to n-1 do
      A[i][j] := 0;
  // Tworzymy tablicę stopni
  SetLength(VD, n);
  // Zerujemy tablicę stopni
  for i := 0 to n-1 do
    VD[i] := 0;
  // Tworzymy tablicę numerów
  SetLength(D, n);
  // Tworzymy pusty stos
  SetLength(S, m+1);
  sptr := 0;
  // Odczytujemy kolejne
  // definicje krawędzi
  for i := 1 to m do
  begin
    // Wierzchołek startowy
    // i końcowy krawędzi
    read(v1, v2);
    // Krawędź v1->v2 obecna
    A[v1][v2] := 1;
    // Krawędź v2->v1 obecna
    A[v2][v1] := 1;
    inc(VD[v1]);
    // Obliczamy
    // stopnie v1 i v2
    inc(VD[v2]);
  end;
  writeln;
  // Szukamy pozycji
  // startowej v1
  for v1 := 0 to n-1 do
    if VD[v1] > 0 then break;
  for i := v1 to n-1 do
    if VD[i] mod 2 = 1 then
    begin
      v1 := i;
      break;
    end;
  // Wyznaczamy cykl
  // lub ścieżkę Eulera
  findEuler(v1);
  // Wypisujemy
  // zawartość stosu
  if VD[v1] mod 2 = 1 then
    write('EULERIAN PATH :')
  else
    write('EULERIAN CYCLE :');
  for i := 0 to sptr-1 do
    write(S[i] :3);
  writeln;
  // Usuwamy tablice dynamiczne
  for i := 0 to n-1 do
    SetLength(A[i], 0);
  SetLength(A, 0);
  SetLength(S, 0);
  SetLength(D, 0);
  SetLength(VD, 0);
end.

// Wyszukiwanie cyklu
// lub ścieżki Eulera
// Algorytm Fleury'ego
// Data: 8.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Zmienne globalne

int n, m, cv, sptr;
// Macierz sąsiedztwa
char **A;
// Stos w tablicy
int *S;
// Tablica numerów wierzchołków
int *D;

// Funkcja wyszukująca mosty
// w grafie
// We:
// v - numer wierzchołka
//     startowego
// vf - ojciec wierzchołka
//      v na drzewie rozpinającym
// Wy:
// Parametr Low dla wierzchołka v
//-------------------------------
int DFSb(int v, int vf)
{
  int Low, temp, i;

  // Numerujemy wierzchołek
  D[v] = cv;
  // Wstępna wartość Low
  Low = cv;
  // Numer dla następnego
  // wierzchołka
  cv++;
  // Przeglądamy sąsiadów v
  for(i = 0; i < n; i++)
    if(A[v][i] && (i != vf))
    {
      // Jeśli sąsiad
      // nieodwiedzony, to
      if(!D[i])
      {
        // to wywołujemy
        // rekurencyjnie DFSb()
        temp = DFSb(i, v);
        // Modyfikujemy Low
        if(temp < Low)
          Low = temp;
      }
      else if(D[i] < Low)
        Low = D[i];
    }
  // Mamy most?
  if((vf > -1) && (Low == D[v]))
    // Oznaczamy krawędź
    // vf-v jako most
    A[vf][v] = A[v][vf] = 2;
  return Low;
}

// Procedura wyszukuje
// cykl lub ścieżkę Eulera
// We:
// v - wierzchołek startowy
//-------------------------
void findEuler(int v)
{
  int u, w, i;

  // W pętli
  // przetwarzamy graf
  while(true)
  {
    // v umieszczamy
    // na stosie
    S[sptr++] = v;
    // Szukamy pierwszego
    // sąsiada v
    for(u = 0; (u < n) &&
               !A[v][u];u++);
    // Nie ma sąsiadów,
    // kończymy
    if(u == n) break;
    for(i = 0; i < n; i++)
      // Zerujemy tablicę D
      D[i] = 0;
    // Numer pierwszego
    // wierzchołka dla DFS
    cv = 1;
    // Identyfikujemy
    // krawędzie-mosty
    DFSb(v, -1);
    // Szukamy krawędzi
    // nie będącej mostem
    for(w = u+1; (A[v][u] == 2) &&
                 (w < n); w++)
      if(A[v][w]) u = w;
    // Usuwamy krawędź v-u
    A[v][u] = A[u][v] = 0;
    // Przechodzimy do u
    v = u;
  }
}

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

int main()
{
  int i, j, v1, v2;
  // Stopnie wierzchołków
  int * VD;
  // Czytamy liczbę
  // wierzchołków i krawędzi
  cin >> n >> m;
  // Tworzymy
  // tablicę wskaźników
  A = new char * [n];
  for(i = 0; i < n; i++)
    // Tworzymy wiersze
    // macierzy sąsiedztwa
    A[i] = new char [n];
  // Macierz
  // wypełniamy zerami
  for(i = 0; i < n; i++)
    for(j = 0; j < n; j++)
      A[i][j] = 0;
  // Tworzymy tablicę stopni
  VD = new int [n];
  // Zerujemy tablicę stopni
  for(i = 0; i < n; i++)
    VD[i] = 0;
  // Tworzymy tablicę numerów
  D = new int [n];
  // Tworzymy pusty stos
  S = new int [m+1];
  sptr = 0;
  // Odczytujemy kolejne
  // definicje krawędzi
  for(i = 0; i < m; i++)
  {
    // Wierzchołek startowy
    // i końcowy krawędzi
    cin >> v1 >> v2;
    // Krawędź v1->v2 obecna
    A[v1][v2] = 1;
    // Krawędź v2->v1 obecna
    A[v2][v1] = 1;
    // Obliczamy
    // stopnie v1 i v2
    VD[v1]++;
    VD[v2]++;
  }
  cout << endl;
  // Szukamy pozycji
  // startowej v1
  for(v1 = 0; v1 < n; v1++)
    if(VD[v1]) break;
  for(i = v1; i < n; i++)
    if(VD[i] % 2)
    {
      v1 = i;
      break;
    }
  // Wyznaczamy cykl
  // lub ścieżkę Eulera
  findEuler(v1);
  // Wypisujemy
  // zawartość stosu
  if(VD[v1] % 2)
    cout << "EULERIAN PATH :";
  else
    cout << "EULERIAN CYCLE :";
  for(i = 0; i < sptr; i++)
    cout << setw(3) << S[i];
  cout << endl;
  // Usuwamy
  // tablice dynamiczne
  for(i = 0; i < n; i++)
    delete [] A[i];
  delete [] A;
  delete [] S;
  delete [] D;
  delete [] VD;
  return 0;
}

' Wyszukiwanie cyklu
' lub ścieżki Eulera
' Algorytm Fleury'ego
' Data: 8.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Zmienne globalne
Dim Shared As Integer n, m, cv, sptr
' Macierz sąsiedztwa
Dim Shared As Byte Ptr Ptr  A
' Stos w tablicy
Dim Shared As Integer Ptr S
' Tablica numerów wierzchołków
Dim Shared As Integer Ptr D

' Funkcja wyszukująca mosty w grafie
' We:
' v - numer wierzchołka startowego
' vf - ojciec wierzchołka v
'      na drzewie rozpinającym
' Wy:
' Parametr Low dla wierzchołka v
'---------------------------------
function DFSb(ByVal v As integer, _
              ByVal vf As integer) _
                       As Integer
   Dim As Integer Low, temp, i

   ' Numerujemy wierzchołek
   D[v] = cv
   ' Wstępna wartość Low
   Low = cv
   ' Numer dla następnego
   ' wierzchołka
   cv += 1
   ' Przeglądamy sąsiadów v
   For i = 0 To n-1
     If (A[v][i] > 0) AndAlso _
        (i <> vf) Then
       ' Jeśli sąsiad
       ' nieodwiedzony, to
       If D[i] = 0 Then
         ' to wywołujemy
         ' rekurencyjnie DFSb()
         temp = DFSb(i, v)
         ' Modyfikujemy Low
         If temp < Low Then _
           Low = temp
       Else
         If D[i] < Low Then _
           Low = D[i]
       End If
     End If
   Next
   ' Mamy most?
   If (vf > -1) AndAlso _
      (Low = D[v]) Then
     ' Oznaczamy krawędź
     ' vf-v jako most
     A[vf][v] = 2: A[v][vf] = 2
   End If
   Return Low
End Function

' Procedura wyszukuje
' cykl lub ścieżkę Eulera
' We:
' v - wierzchołek startowy
'-------------------------
Sub findEuler(ByVal v As integer)
  Dim As Integer u, w, i

  ' W pętli przetwarzamy graf
  While 1
    ' v umieszczamy na stosie
    S[sptr] = v
    sptr += 1
    u = 0
    ' Szukamy pierwszego sąsiada v
    While (u < n) AndAlso _
          (A[v][u] = 0)
      u += 1
    Wend
    ' Nie ma sąsiadów, kończymy
    If u = n Then Exit While
    For i = 0 To n-1
      ' Zerujemy tablicę D
      D[i] = 0
    Next
    ' Numer pierwszego
    ' wierzchołka dla DFS
    cv = 1
    ' Identyfikujemy krawędzie-mosty
    DFSb(v, -1)
    ' Szukamy krawędzi
    ' nie będącej mostem
    w = u+1
    While (A[v][u] = 2) AndAlso _
          (w < n)
      If A[v][w] > 0 Then u = w
      w += 1
    Wend
    ' Usuwamy krawędź v-u
    A[v][u] = 0: A[u][v] = 0
    ' Przechodzimy do u
    v = u
  Wend
End Sub

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

Dim As Integer i, j, v1, v2
' Stopnie wierzchołków
Dim As Integer Ptr VD

Open Cons For Input As #1
' Czytamy liczbę
' wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablicę wskaźników
A = New Byte Ptr [n]
For i = 0 To n-1
  ' Tworzymy wiersze
  ' macierzy sąsiedztwa
  A[i] = New Byte [n]
Next
' Macierz wypełniamy zerami
For i = 0 To n-1
  For j = 0 To n-1
    A[i][j] = 0
  Next
Next
' Tworzymy tablicę stopni
VD = New integer [n]
' Zerujemy tablicę stopni
For i = 0 To n-1
  VD[i] = 0
Next
' Tworzymy tablicę numerów
D = New integer [n]
' Tworzymy pusty stos
S = New integer [m+1]
sptr = 0
' Odczytujemy kolejne
' definicje krawędzi
For i = 0 To m-1
  ' Wierzchołek startowy
  ' i końcowy krawędzi
  Input #1, v1, v2
  ' Krawędź v1->v2 obecna
  A[v1][v2] = 1
  ' Krawędź v2->v1 obecna
  A[v2][v1] = 1
  ' Obliczamy stopnie v1 i v2
  VD[v1] += 1
  VD[v2] += 1
Next
Close #1
Print
' Szukamy pozycji startowej v1
v1 = 0
While v1 < n
  If VD[v1] > 0 Then Exit While
  v1 += 1
Wend
For i = v1 To n-1
  If VD[i] Mod 2 = 1 Then
    v1 = i
    Exit For
  End If
Next
' Wyznaczamy cykl lub ścieżkę Eulera
findEuler(v1)
' Wypisujemy zawartość stosu
If VD[v1] Mod 2 = 1 Then
  Print "EULERIAN PATH :";
Else
  Print "EULERIAN CYCLE :";
End If
For i = 0 To sptr-1
  Print Using "###";S[i];
Next
Print
' Usuwamy tablice dynamiczne
For i = 0 To n-1
  Delete [] A[i]
Next
Delete [] A
Delete [] S
Delete [] D
Delete [] VD
End

# Wyszukiwanie cyklu
# lub ścieżki Eulera
# Algorytm Fleury#ego
# Data: 6.02.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Funkcja wyszukująca mosty w grafie
# We:
# v - numer wierzchołka startowego
# vf - ojciec wierzchołka v
#      na drzewie rozpinającym
# Wy:
# Parametr Low dla wierzchołka v
#---------------------------------
def dfs_b(v, vf):
    global d,cv,a,n
    # Numerujemy wierzchołek
    d[v] = cv
    # Wstępna wartość Low
    low = cv
    # Numer dla następnego
    # wierzchołka
    cv += 1
    # Przeglądamy sąsiadów v
    for i in range(n):
        if (a[v][i] > 0) and (i != vf):
           # Jeśli sąsiad
           # nieodwiedzony, to
           if not d[i]:
              # to wywołujemy
              # rekurencyjnie DFSb()
              temp = dfs_b(i, v)
              # Modyfikujemy Low
              if temp < low:
                 low = temp
           else:
              if d[i] < low:
                 low = d[i]
    # Mamy most?
    if (vf > -1) and (low == d[v]):
        # Oznaczamy krawędź
        # vf-v jako most
        a[vf][v] = 2
        a[v][vf] = 2
    return low


# Procedura wyszukuje
# cykl lub ścieżkę Eulera
# We:
# v - wierzchołek startowy
#-------------------------
def find_euler(v):
    global s,sptr,a,n,cv,d
    # W pętli przetwarzamy graf
    while True:
       # v umieszczamy na stosie
       s[sptr] = v
       sptr += 1
       u = 0
       # Szukamy pierwszego sąsiada v
       while (u < n) and not a[v][u]:
          u += 1
       # Nie ma sąsiadów, kończymy
       if u == n: break
       # Zerujemy tablicę D
       d = [0] * n
       # Numer pierwszego
       # wierzchołka dla DFS
       cv = 1
       # Identyfikujemy krawędzie-mosty
       dfs_b(v, -1)
       # Szukamy krawędzi
       # nie będącej mostem
       w = u+1
       while (a[v][u] == 2) and (w < n):
          if a[v][w] > 0:
              u = w
          w += 1
       # Usuwamy krawędź v-u
       a[v][u] = 0
       a[u][v] = 0
       # Przechodzimy do u
       v = u


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

# Czytamy liczbę
# wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablicę wskaźników
a = [None] * n
for i in range(n):
    # Tworzymy wiersze
    # macierzy sąsiedztwa
    a[i] = [0] * n
# Tworzymy tablicę stopni
vd = [0] * n
# Tworzymy tablicę numerów
d = [0] * n
# Tworzymy pusty stos
s = [0] * (m+1)
sptr = 0
# 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])
    # Krawędź v1->v2 obecna
    a[v1][v2] = 1
    # Krawędź v2->v1 obecna
    a[v2][v1] = 1
    # Obliczamy stopnie v1 i v2
    vd[v1] += 1
    vd[v2] += 1
print()
# Szukamy pozycji startowej v1
v1 = 0
while v1 < n:
    if vd[v1] > 0: break
    v1 += 1
for i in range(v1,n):
    if vd[i] % 2:
       v1 = i
       break
cv = 1
# Wyznaczamy cykl lub ścieżkę Eulera
find_euler(v1)
# Wypisujemy zawartość stosu
if vd[v1] % 2:
    print("EULERIAN PATH :", end=" ")
else:
    print("EULERIAN CYCLE :", end=" ")
for i in range(sptr):
    print("%3d" % s[i], end="")
print()
# Usuwamy tablice dynamiczne
del a, s, d, vd

// Wyszukiwanie cyklu lub
// ścieżki Eulera
// Algorytm Hierholzera
// Data: 10.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

program hierholzer;

// Typy danych
type
  // wiersz macierzy sąsiedztwa
  nptr = array of byte;

  // Wskaźnik elementów
  // listy dwukierunkowej
  PDLel = ^DLel;
  DLel =  record
    next  : PDLel;
    prev  : PDLel;
    v     : integer;
  end;

// Zmienne globalne
var
  // Liczba krawędzi i wierzchołków
  m, n : integer;
  // Dynamiczna macierz sąsiedztwa
  graf: array of nptr;
  // Tablica odwiedzin
  vs : array of boolean;

// Procedury obsługi
// listy dwukierunkowej
//---------------------

// Procedura dołącza do listy
// nowy element za elementem
// wskazywanym przez p
//---------------------------
procedure addC(x : integer;
               p : PDLel);
var
  r : PDLel;
begin
  new(r);
  r^.v := x;
  r^.next := p^.next;
  if r^.next <> nil then
    r^.next^.prev := r;
  r^.prev := p;
  p^.next := r;
end;

// Procedura usuwa z listy
// element wskazywany przez p
//---------------------------
procedure remC (p : PDLel);
begin
  if p^.next <> nil then
    p^.next^.prev := p^.prev;
  if p^.prev <> nil then
    p^.prev^.next := p^.next;
  dispose(p);
end;

// Rekurencyjna funkcja dodająca
// do listy nowy cykl
// v - wierzchołek startowy
//     i końcowy cyklu
// w - wierzchołek bieżący
// p - referencja do wskazania
//     punktu wstawiania na liście
//--------------------------------
function DFSaddCycle(v, w : integer;
                    var p : PDLel)
                          : boolean;
var
  u : integer;
begin
  // Oznaczamy v jako odwiedzony
  vs[w] := true;
  // Dodajemy w do cyklu
  addC(w, p);
  // p wskazuje dodany element
  p := p^.next;
  // Przeglądamy sąsiadów w
  for u := 0 to n-1 do
    if graf[w][u] = 1 then
    begin
      // Cykl znaleziony?
      if u = v then
      begin
        // Zamykamy cykl na liście C
        addC(v, p);
        repeat
          // Usuwamy krawędzie cyklu
          graf[p^.v][p^.next^.v] := 0;
          if p^.v = v then Exit(true);
          p := p^.prev;
        until false;
      end;
      if not vs[u] and
         DFSaddCycle(v, u, p) then
        Exit(true);
    end;
  // Z listy usuwamy w
  p := p^.prev;
  remC(p^.next);
  DFSaddCycle := false;
end;

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

var
  i, j, v1, v2 : integer;
  // Lista cyklu Eulera
  C : PDLel;
  p : PDLel;
begin
  // Czytamy liczbę
  // wierzchołków i krawędzi
  read(n, m);
  // Tworzymy tablice dynamiczne
  SetLength(graf, n);
  SetLength(vs, n);
  for i := 0 to n-1 do
  begin
    SetLength(graf[i], n);
    for j := 0 to n-1 do
      graf[i][j] := 0;
  end;
  // Odczytujemy definicje
  // krawędzi grafu
  for i := 0 to m-1 do
  begin
    read(v1, v2);
    graf[v1][v2] := 1;
  end;
  // Tworzymy listę
  // z wierzchołkiem v1
  new(c);
  C^.v := v1;
  C^.next := nil;
  C^.prev := nil;
  // p wskazuje pierwszy
  // element listy
  p := C;
  // Przeglądamy listę C
  while p <> nil do
  begin
    // Szukamy sąsiadów
    for i := 0 to n-1 do
      if graf[p^.v][i] = 1 then
      begin
        for j := 0 to n-1 do
          vs[j] := false;
        // Dla każdego sąsiada
        // uruchamiamy szukanie
        // cyklu
        DFSaddCycle(p^.v, i, p);
      end;
    // Następny element listy C
    p := p^.next;
  end;
  writeln;
  // Wyświetlamy zawartość listy C,
  // czyli pełny cykl Eulera
  p := C;
  while p <> nil do
  begin
    write(p^.v:3);
    p := p^.next;
  end;
  writeln;
  // Usuwamy zmienne dynamiczne
  p := C;
  while p <> nil do
  begin
    p := C^.next;
    remC(c);
    C := p;
  end;
  for i := 0 to n-1 do
    SetLength(graf[i], 0);
  SetLength(graf, 0);
  SetLength(vs, 0);
end.

// Wyszukiwanie cyklu lub
// ścieżki Eulera
// Algorytm Hierholzera
// Data: 10.02.2014
// (C)2014 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>

using namespace std;

// Typy danych
struct DLel
{
  DLel *next, *prev;
  int v;
};

// Zmienne globalne
//-----------------
// Liczba krawędzi i wierzchołków
int m, n;
// Dynamiczna macierz sąsiedztwa
char **graf;
// Tablica odwiedzin
bool * vs;

// Procedury obsługi listy
// dwukierunkowej
//------------------------

// Procedura dołącza do listy
// nowy element za elementem
// wskazywanym przez p
//---------------------------
void addC(int x, DLel *p)
{
  DLel * r;

  r = new DLel;
  r->v = x;
  r->next = p->next;
  if(r->next)
    r->next->prev = r;
  r->prev = p;
  p->next = r;
}

// Procedura usuwa z listy
// element wskazywany przez p
//---------------------------
void remC(DLel *p)
{
  if(p->next)
    p->next->prev = p->prev;
  if(p->prev)
    p->prev->next = p->next;
  delete p;
}

// Rekurencyjna funkcja dodająca
// do listy nowy cykl
// v - wierzchołek startowy
//     i końcowy cyklu
// w - wierzchołek bieżący
// p - referencja do wskazania
//     punktu wstawiania na liście
//--------------------------------
bool DFSaddCycle(int v,
                 int w,
                 DLel * & p)
{
  int u;

  // Oznaczamy v jako odwiedzony
  vs[w] = true;
  // Dodajemy w do cyklu
  addC(w, p);
  // p wskazuje dodany element
  p = p->next;
  // Przeglądamy sąsiadów w
  for(u = 0; u < n; u++)
    if(graf[w][u])
    {
      // Cykl znaleziony?
      if(u == v)
      {
        // Zamykamy cykl na liście C
        addC(v, p);
        do
        {
          // Usuwamy krawędzie cyklu
          graf[p->v][p->next->v] = 0;
          if(p->v == v) return true;
          p = p->prev;
        } while(true);
      }
      if(!vs[u] &&
         DFSaddCycle(v, u, p))
        return true;
    }
  // Z listy usuwamy w
  p = p->prev;
  remC(p->next);
  return false;
}

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

int main()
{
  int i, j, v1, v2;
  DLel *C, *p;

  // Czytamy liczbę wierzchołków
  // i krawędzi
  cin >> n >> m;
  // Tworzymy tablice dynamiczne
  graf = new char * [n];
  vs = new bool [n];
  for(i = 0; i < n; i++)
  {
    graf[i] = new char [n];
    for(j = 0; j < n; j++)
      graf[i][j] = 0;
  }
  // Odczytujemy definicje
  // krawędzi grafu
  for(i = 0; i < m; i++)
  {
    cin >> v1 >> v2;
    graf[v1][v2] = 1;
  }
  // Tworzymy listę
  // z wierzchołkiem v1
  C = new DLel;
  C->v = v1;
  C->next = nullptr;
  C->prev = nullptr;
  // Przeglądamy listę C
  for(p = C; p; p = p->next)
    // Szukamy sąsiadów
    for(i = 0; i < n; i++)
      if(graf[p->v][i])
      {
        for(j = 0; j < n; j++)
          vs[j] = false;
        // Dla każdego sąsiada
        // uruchamiamy szukanie
        // cyklu
        DFSaddCycle(p->v, i, p);
      }
  cout << endl;
  // Wyświetlamy zawartość listy C,
  // czyli pełny cykl Eulera
  for(p = C; p; p = p->next)
    cout << setw(3) << p->v;
  cout << endl;
  // Usuwamy zmienne dynamiczne
  p = C;
  while(p)
  {
    p = C->next;
    remC(C);
    C = p;
  }
  for(i = 0; i < n; i++)
    delete [] graf[i];
  delete [] graf;
  delete [] vs;
  return 0;
}

' Wyszukiwanie cyklu lub ścieżki Eulera
' Algorytm Hierholzera
' Data: 10.02.2014
' (C)2014 mgr Jerzy Wałaszek
'---------------------------

' Typy danych
Type DLel
  Next As DLel Ptr
  prev As DLel Ptr
  v As Integer
End Type

' Zmienne globalne
' Liczba krawędzi i wierzchołków
Dim Shared As Integer m, n
' Dynamiczna macierz sąsiedztwa
Dim Shared As Byte Ptr Ptr graf
' Tablica odwiedzin
Dim Shared As Byte Ptr vs

' Procedury obsługi listy dwukierunkowej
'---------------------------------------

' Procedura dołącza do listy nowy element
' za elementem wskazywanym przez p
'----------------------------------------
Sub addC(ByVal x As Integer, _
         ByVal p As DLel Ptr)
  Dim As DLel Ptr r

  r = new DLel
  r->v = x
  r->next = p->next
  If r->next Then r->next->prev = r
  r->prev = p
  p->next = r
End Sub

' Procedura usuwa z listy element
' wskazywany przez p
'--------------------------------
Sub remC(ByVal p As DLel Ptr)

  If p->next Then p->next->prev = p->prev
  If p->prev Then p->prev->next = p->next
  Delete p
End Sub

' Rekurencyjna funkcja dodająca
' do listy nowy cykl
' v - wierzchołek startowy i końcowy cyklu
' w - wierzchołek bieżący
' p - referencja do wskazania punktu
'     wstawiania na liście
'-----------------------------------------
Function DFSaddCycle(ByVal v As integer, _
                     ByVal w As integer, _
                     ByRef p As DLel Ptr) _
                             As Integer
  Dim As Integer u

  ' Oznaczamy v jako odwiedzony
  vs[w] = 1
  ' Dodajemy w do cyklu
  addC(w, p)
  ' p wskazuje dodany element
  p = p->next
  ' Przeglądamy sąsiadów w
  For u = 0 To n-1
    If graf[w][u] > 0 Then
      ' Cykl znaleziony?
      If u = v Then
        ' Zamykamy cykl na liście C
        addC(v, p)
        Do
          ' Usuwamy krawędzie cyklu
          graf[p->v][p->next->v] = 0
          If p->v = v then return 1
          p = p->prev
        Loop While 1
      End If
      If (vs[u] = 0) AndAlso _
         (DFSaddCycle(v, u, p) = 1) Then _
        Return 1
    End If
  Next
  ' Z listy usuwamy w
  p = p->prev
  remC(p->next)
  return 0
End Function

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

Dim As integer i, j, v1, v2
Dim As DLel Ptr p, C

Open Cons For Input As #1
' Czytamy liczbę wierzchołków i krawędzi
Input #1, n, m
' Tworzymy tablice dynamiczne
graf = New Byte Ptr [n]
vs = New Byte [n]
For i = 0 To n-1
  graf[i] = New Byte [n]
  For j = 0 To n-1
    graf[i][j] = 0
  Next
Next
' Odczytujemy definicje krawędzi grafu
For i = 0 To m-1
  Input #1, v1, v2
  graf[v1][v2] = 1
Next
Close #1
' Tworzymy listę z wierzchołkiem v1
C = New DLel
C->v = v1
C->next = 0
C->prev = 0
p = C
' Przeglądamy listę C
While p
  ' Szukamy sąsiadów
  For i = 0 To n-1
    If graf[p->v][i] = 1 Then
      For j = 0 To n-1
        vs[j] = 0
      Next
      ' Dla każdego sąsiada
      ' uruchamiamy szukanie cyklu
      DFSaddCycle(p->v, i, p)
    End If
  Next
  p = p->Next
Wend
Print
' Wyświetlamy zawartość listy C,
' czyli pełny cykl Eulera
p = C
while p <> 0
  Print Using "###";p->v;
  p = p->next
Wend
Print
' Usuwamy zmienne dynamiczne
p = C
While p
  p = C->next
  remC(C)
  C = p
Wend
For i = 0 To n-1
  Delete [] graf[i]
Next
Delete [] graf
Delete [] vs
End

# Wyszukiwanie cyklu lub ścieżki Eulera
# Algorytm Hierholzera
# Data: 10.02.2025
# (C)2025 mgr Jerzy Wałaszek
#---------------------------

# Klasa listy
class DLel:
    def __init__(self):
        self.next = None
        self.prev = None
        self.v = 0


# Procedury obsługi listy dwukierunkowej
#---------------------------------------
# Dołącza do listy nowy element
# za elementem wskazywanym przez p
def addc(x, p):
    r = DLel()
    r.v = x
    r.next = p.next
    if r.next:
        r.next.prev = r
    r.prev = p
    p.next = r


# Usuwa z listy element
# wskazywany przez p
def  remc(p):
    if p.next:
        p.next.prev = p.prev
    if p.prev:
        p.prev.next = p.next
    del p


# Rekurencyjna funkcja dodająca
# do listy nowy cykl
# v - wierzchołek startowy i końcowy cyklu
# w - wierzchołek bieżący
# p - referencja do wskazania punktu
#     wstawiania na liście
#-----------------------------------------
def dfs_add_cycle(v ,w ,p):
    global vs,n,graf
    # Oznaczamy v jako odwiedzony
    vs[w] = True
    # Dodajemy w do cyklu
    addc(w, p)
    # p wskazuje dodany element
    p = p.next
    # Przeglądamy sąsiadów w
    for u in range(n):
        if graf[w][u] > 0:
            # Cykl znaleziony?
            if u == v:
                # Zamykamy cykl na liście C
                addc(v, p)
                while True:
                    # Usuwamy
                    # krawędzie cyklu
                    graf[p.v][p.next.v] = 0
                    if p.v == v:
                        return True
                    p = p.prev
            if not vs[u] and \
               dfs_add_cycle(v,u,p):
                return True
    # Z listy usuwamy w
    p = p.prev
    remc(p.next)
    return False


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

# Czytamy liczbę wierzchołków i krawędzi
x = input().split()
n = int(x[0])
m = int(x[1])
# Tworzymy tablice dynamiczne
graf = [None] * n
vs = [False] * n
for i in range(n):
    graf[i] = [0] * n
# Odczytujemy definicje krawędzi grafu
for i in range(m):
    x = input().split()
    v1 = int(x[0])
    v2 = int(x[1])
    graf[v1][v2] = 1
# Tworzymy listę z wierzchołkiem v1
c = DLel()
c.v = v1
p = c
# Przeglądamy listę C
while p:
    # Szukamy sąsiadów
    for i in range(n):
        if graf[p.v][i] == 1:
            for j in range(n):
                vs[j] = False
            # Dla każdego sąsiada
            # uruchamiamy szukanie cyklu
            dfs_add_cycle(p.v, i, p)
    p = p.next
print()
# Wyświetlamy zawartość listy C,
# czyli pełny cykl Eulera
p = c
while p:
    print("%3d" % p.v, end="")
    p = p.next
print()
# Usuwamy zmienne dynamiczne
p = c
while p:
    p = c.next
    remc(c)
    c = p
for i in range(n):
    graf[i] = None
del graf, vs